Python solutions (dfs+stack, bfs+queue, dfs recursively).


  • 48
    C
    # dfs + stack
    def binaryTreePaths1(self, root):
        if not root:
            return []
        res, stack = [], [(root, "")]
        while stack:
            node, ls = stack.pop()
            if not node.left and not node.right:
                res.append(ls+str(node.val))
            if node.right:
                stack.append((node.right, ls+str(node.val)+"->"))
            if node.left:
                stack.append((node.left, ls+str(node.val)+"->"))
        return res
        
    # bfs + queue
    def binaryTreePaths2(self, root):
        if not root:
            return []
        res, queue = [], collections.deque([(root, "")])
        while queue:
            node, ls = queue.popleft()
            if not node.left and not node.right:
                res.append(ls+str(node.val))
            if node.left:
                queue.append((node.left, ls+str(node.val)+"->"))
            if node.right:
                queue.append((node.right, ls+str(node.val)+"->"))
        return res
        
    # dfs recursively
    def binaryTreePaths(self, root):
        if not root:
            return []
        res = []
        self.dfs(root, "", res)
        return res
    
    def dfs(self, root, ls, res):
        if not root.left and not root.right:
            res.append(ls+str(root.val))
        if root.left:
            self.dfs(root.left, ls+str(root.val)+"->", res)
        if root.right:
            self.dfs(root.right, ls+str(root.val)+"->", res)

  • 0
    F

    Very good explanation!


  • 0
    Z

    thx very useful


  • 0
    G

    your codes are sooooooooo beautiful, you are sooooo smart !!!


  • 0
    G

    Hi, I have tried your second method and I think it is not correct, although it passes all test cases.
    Take the example [1,2,3,4,5,null,null], the result should be [124, 125, 13], but the second method will return [13,124,125]. So I think dfs is necessary for this question.


  • 0
    G

    @gswgdanb is right.
    because level order tend to output the leaf in lower level first.


  • 0
    Y

    Aren't the two ([124, 125, 13] and [13,124,125]) equivalent given the scope of the question?


  • 0

    this is my java solutions (dfs + stack , dfs recursion .)
    bfs+ queue is similar with dfs+stack , so I don't need to complete it .
    :)

        public List<String> binaryTreePaths(TreeNode root) {
            List<String> ret = new ArrayList<>();
            if(root == null){
                return ret;
            }
            
            Stack<TreeNode> stack = new Stack<>();
            Stack<String> path_stack = new Stack<>();
    
            stack.push(root);
            path_stack.push(root.val+"");
            
            while(!stack.isEmpty()){
                TreeNode node = stack.pop();
                String path = path_stack.pop();
                
                if(node.right == null && node.left == null){
                    ret.add(path);
                }else{
                    if(node.left != null){
                        stack.push(node.left);
                        path_stack.push(path + "->"+node.left.val);
                    }
                    if(node.right != null){
                        stack.push(node.right);
                        path_stack.push(path + "->"+node.right.val);
                    }
                }
            }
            
            //helper(ret, "", root);
            return ret;
        }
    
    private void helper(List<String> result, String path, TreeNode node){
            if(node == null){
                return;
            }
            if(node.left == null && node.right == null){
                result.add(path+node.val);
                return;
            }
            path += node.val + "->";
            helper(result, path, node.left);
            helper(result, path, node.right);
        }
    

  • 0
    J

    I feel like the DFS + stack approach still uses BFS, because it visited the leaves at the same level first. Any comment on that?


  • 0
    H

    Hi folks, I have the following code. It is almost the same as the correct code, but it gives wrong answer. I think the problem is at the line:

    t = t+str(root.val)+"->"
    self.traversTree(root.right, o, t)

    In the correct answer it is like this:

    self.traversTree(root.right, o, t+str(root.val)+"->")

    My code always give me this result:
    input: [1,2,3,null,5]
    my answer: ["1->2->5","1->1->3"]
    expected answer: ["1->2->5","1->3"]

    I don't know why, could you please help me! Thank you!
    Here is my code:

    class Solution(object):
    def binaryTreePaths(self, root):
    """
    :type root: TreeNode
    :rtype: List[str]
    """
    output = []
    tmp = ""
    if root:
    self.traversTree(root, output, tmp)
    return output

    def traversTree(self, root, o,t):
        if not root.left and not root.right:
            o.append(t+str(root.val))
            
        if root.left:
            t = t+str(root.val)+"->"
            self.traversTree(root.left, o, t)
        
            
        if root.right:
            t = t+str(root.val)+"->"
            self.traversTree(root.right, o, t)

  • 0
    B

    @haihaicode
    Pay attention to the variable t in the function traverseTree. Based on the example you mentioned, when the program finishes root.left part (including all its recursions inside), t equals to "1->" instead of "". t was already initialized in the block:

    if root.left:
            t = t+str(root.val)+"->" # here
    

    That is why you always get part of your output like "1->1->3" instead of "1->3".


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.