LeetCode 257 [Binary Tree Paths]

原题

给一棵二叉树，找出从根节点到叶子节点的所有路径。

样例
给出下面这棵二叉树：

   1
 /   \
2     3
 \
  5

所有根到叶子的路径为：

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

解题思路

• 二叉树遍历问题
• 如果当前节点的左儿子和右儿子都为None => 说明当前节点为一个根节点，输出一条路径
• 如果当前节点有左儿子，带着path向左进行。如果有右儿子，带着path向右进行

完整代码

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

class Solution:
    # @param {TreeNode} root
    # @return {string[]}
    def binaryTreePaths(self, root):
        if not root:
            return []
        res = []
        self.helper(root, [], res)
        return res
        
    def helper(self, root, path, res):
        if root.left is None and root.right is None:
            res.append("".join(path + [str(root.val)]))
            return
        if root.left:
            self.helper(root.left, path + [str(root.val)+"->"], res)
        if root.right:
            self.helper(root.right, path + [str(root.val)+"->"], res)