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

• ``````# 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)``````

• Very good explanation!

• thx very useful

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

• 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.

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

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

• 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){
}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){
return;
}
path += node.val + "->";
helper(result, path, node.left);
helper(result, path, node.right);
}
``````

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

• 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]

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)``````

• @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".

• same thought, more readable recursion

``````    def binaryTreePaths(self, root):
if not root:
return []
res = []
self.path(root,'',res)
return res

def path(self,root,string,res):

string += str(root.val)

if root.left:
self.path(root.left,string+'->',res)

if root.right:
self.path(root.right,string+'->',res)

if not root.left and not root.right:
res.append(string)
``````

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