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
Source
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def binary_tree_paths(root):
"""recursive solution using DFS (preorder traversal)"""
def dfs(node, path):
nonlocal result
if not node:
return
tmp_path = path + [node.val]
if not node.left and not node.right:
result += tmp_path, # here as opposed to above to avoide
return # duplicate paths (+ wrong when only 1 child)
dfs(node.left, tmp_path)
dfs(node.right, tmp_path)
result = []
dfs(root, [])
result = ["->".join(map(str, path)) for path in result]
return result
def binary_tree_paths(root):
"""alternative version of above solution"""
def dfs(node, path):
nonlocal result
if not node.left and not node.right:
result += path,
return
if node.left:
dfs(node.left, path + "->" + str(node.left.val))
if node.right:
dfs(node.right, path + "->" + str(node.right.val))
if not root:
return []
result = []
dfs(root, str(root.val))
return result
Solve it both recursively and iteratively.
def binary_tree_paths(root):
"""iterative solution using DFS (preorder traversal)"""
if not root:
return []
stack = [(root, [])]
result = []
while stack:
node, path = stack.pop()
if not node:
continue
tmp_path = path + [node.val]
if not node.left and not node.right:
result += tmp_path,
stack += (node.right, tmp_path), (node.left, tmp_path),
result = ["->".join(map(str, path)) for path in result]
return result
def binary_tree_paths(root):
"""alternative version of above solution"""
if not root:
return []
stack = [(root, str(root.val))]
result = []
while stack:
node, path = stack.pop()
if not node.left and not node.right:
result += path,
if node.right:
stack += (node.right, path + "->" + str(node.right.val)),
if node.left:
stack += (node.left, path + "->" + str(node.left.val)),
return result
def binary_tree_paths(root):
"""iterative solution using BFS (level traversal)"""
if not root:
return []
queue = [(root, str(root.val))]
result = []
for node, path in queue:
if not node.left and not node.right:
result += path,
if node.left:
queue += (node.left, path + "->" + str(node.left.val)),
if node.right:
queue += (node.right, path + "->" + str(node.right.val)),
return(result)