0257. Binary Tree Paths - chasel2361/leetcode GitHub Wiki

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children. Example:
Input: [1,2,3,null,5]
Output: ["1->2->5", "1->3"]
Explanation: All root-to-leaf paths are: 1->2->5, 1->3

這題要求回傳給定二元數由根到葉的所有路徑，這可以用遞迴法來解決，只要利用一個暫存變數儲存已走過的路徑，每往前一個節點更新一次直到盡頭

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> list:
        if not root:
            return []        
        res = []
        self.get_path(root, "", res)
        return res
    
    def get_path(self, root: TreeNode, path: str, res: list):
        """
        Paramaters:
            root: The TreeNode which need to get path.
            path: A temporary arg records the path to root.
            res: Result list obj which record all the path in this tree.
        """
        if not root.left and not root.right:
            res.append(path + str(root.val))            
        tmp = path + str(root.val) + "->" 
        if root.left:
            self.get_path(root.left, tmp, res)
        if root.right:
            self.get_path(root.right, tmp, res)

這樣寫的時間複雜度為 O(N)， 空間複雜度會因為 tmp 這個暫存變數在遞迴路徑中出現很多個，占掉不少空間，變成 O(N**2)。

如果換個想法，改變 path 的使用方式，當檢查到葉子的時候就把 path 的末項刪除，如此一來這個變數就可以重複使用，不需要每次遞迴就產生一個新的。 另外，還可以使用 str.join(iterable) 這個函式，他可以將輸入的可迭代變數以呼叫的 str 連接，因此 path 可以保持較為彈性的 list 型態。

class Solution:
    def binaryTreePaths(self, root: TreeNode) -> list(str):
        if not root:
            return []        
        res = []
        path = []
        self.get_path(root, path, res)
        return res
    
    def get_path(self, root: TreeNode, path: list, res: list):
        """
        Parameters:
            root: The TreeNode which need to get path.
            path: A temporary arg records the path to root which will be delete when 
                the root turns out to be leaf.
            res: Result list obj which record all the path in this tree.
        """
        path.append(str(root.val))
        if root.left:
            self.get_path(root.left, path, res)
        if root.right:
            self.get_path(root.right, path, res)
        if not root.left and not root.right:
            res.append("->".join(path))
        path.pop()

改進之後時間複雜度沒有改變，仍為O(N)，但空間複雜度有一定程度的下降，path 為 O(N)，res 為 O(NlogN)，最終為 O(NlogN)