Given a binary tree, return all root-to-leaf paths.
Note: A leaf is a node with no children.
Example:
Input: 1
/ \
2 3
\
5 Output: ["1->2->5", "1->3"] Explanation: All root-to-leaf paths are: 1->2->5, 1->3 思路为DFS, 只是append进入stack的时候一并append进入当前的path即可. 1. Constraints
1) can be empty 2. Ideas
DFS T: O(n) S: O(n)
1) edge case
2) stack = [(root, str(root.val))]
3) DFS, if leaf, ans.append(path)
4)return ans 3. Codes
3.1) iterable
class Solution:
def path(self, root):
if not root: return []
ans, stack = [], [(root, str(root.val))]
while stack
node, path = stack.pop()
if not node.left and not node.right:
ans.append(path)
if node.right:
stack.append((node.right, path + "->" + node.right.val))
if node.left:
stack.append((node.left, path + "->" + node.left.val))
return ans
3.2) Recursive
class Solution:
def path(self, root):
def helper(root, path, ans):
path += str(root.val)
if not root.left and not root.right:
ans.append(path)
if root.left:
stack.append((root.left, path + "->", ans))
if root.right:
stack.append((root.right, path + "->", ans))
if not root: return []
ans = []
helper(root, "", ans)
return ans
4.. Test cases
1) empty
2) 1
3)
1
/ \
2 3
\
5