257_Binary Tree Paths

257. Binary Tree Paths

Level: easy

Tag: tree, dfs

Question

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

Example 1

given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

Solution 1: recursive

递归实现深度优先遍历。注意要记录途中访问过的节点，遇到叶子节点时可以生成一条路径字符串。关于记录路径，先保存在数组里,需要生成路径时再生成。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        ret = []
        path_list = []
        self.dfs(root, path_list, ret)
        return ret

    def dfs(self, root, path_list, ret):
        if not root:
            return []
        path_list.append(str(root.val))      # use str() to convert integear to string for join next step
        if not root.left and not root.right:
            ret.append('->'.join(path_list))
        if root.left:
            self.dfs(root.left, path_list, ret)
        if root.right:
            self.dfs(root.right, path_list, ret)
        path_list.pop()                # pop here to pop both leaf and node

Another version (w/o defining a helper function)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        ret = []
        if not root:
            return ret
        if not root.left and not root.right:
            ret.append(str(root.val))
            return ret
        for path in self.binaryTreePaths(root.left):
            ret.append(str(root.val) + "->" + path) 
        for path in self.binaryTreePaths(root.right):
            ret.append(str(root.val) + "->" + path)
        return ret

Solution 2: iterative (Depth first search, using stack)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        ret, stack = [], [(root, '')]
        while stack:
            node, curs = stack.pop()
            if node:
                if not node.left and not node.right:
                    ret.append(curs + str(node.val))                
                stack.append((node.right, curs + str(node.val) + '->'))
                stack.append((node.left, curs + str(node.val) + '->'))
        return ret

Solution 3: iterative (Breadth first search, using stack) ??

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        ret, queue = [], [(root, '')]
        while queue:
            node, curs = queue.pop()
            if node:
                if not node.left and not node.right:
                    ret.append(curs + str(node.val))
                queue.insert(0, (node.left, curs + str(node.val) + '->'))
                queue.insert(0, (node.right, curs + str(node.val) + '->'))
        return ret