257. Binary Tree Paths

题目描述和难度

• 题目描述：

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

• 题目难度：简单。
• 英文网址：257. Binary Tree Paths 。
• 中文网址：257. 二叉树的所有路径 。

思路分析

求解关键：

参考解答

参考解答1：从根结点向下递归执行，把沿途经过的结点都存在 path 这个字符串里，直到走到叶子结点才进行结算。

Python 写法：

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

class Solution:

    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """

        res = []
        if root is None:
            return res
        self.__helper(root, '', res)
        return res

    def __helper(self, node, pre, res):
        # 叶子结点
        if node.left is None and node.right is None:
            res.append(pre  + str(node.val))
            return
        if node.left:
            self.__helper(node.left, pre + str(node.val) + '->', res)
        if node.right:
            self.__helper(node.right, pre + str(node.val) + '->', res)

参考解答2：使用回溯的办法，想象 path 就是一个绳子，一条路走到底以后，就要释放。

# 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]
        """

        res = []
        if root is None:
            return res
        path = []
        self.__helper(root, path, res)
        return res

    def __helper(self, node, path, res):
        """
        :param node:
        :param path: 沿途经过的结点值组成的列表
        :param res: 存放最终结果的变量
        :return:
        """
        if node is None:
            return
        path.append(str(node.val))
        if node.left is None and node.right is None:
            # 可以结算了
            res.append("->".join(path))
            return
        if node.left:
            self.__helper(node.left, path, res)

            # 【重点】：回溯的时候，要记得弹出
            # 左边结点都看过了，所以 path 要弹出
            path.pop()

        if node.right:
            self.__helper(node.right, path, res)

            # 【重点】：回溯的时候，要记得弹出
            # 右边结点都看过了，所以 path 要弹出
            path.pop()

参考解答3：下面这个写法是后序遍历的做法，先把左右子结点遍历完成以后，再处理自己。我个人觉得不是很好理解，但是这个思路还是值得学习的。

Java 代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        // 这个节点是个根节点，想一想只有一个元素的情况
        if (root.left == null && root.right == null) {
            res.add(String.valueOf(root.val));
        }

        List<String> leftS = binaryTreePaths(root.left);
        for (int i = 0; i < leftS.size(); i++) {
            res.add(String.valueOf(root.val) + "->" + leftS.get(i));
        }
        List<String> rightS = binaryTreePaths(root.right);
        for (int i = 0; i < rightS.size(); i++) {
            res.add(String.valueOf(root.val) + "->" + rightS.get(i));
        }
        return res;
    }
}

Python 写法：

# 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]
        """

        res = []
        # 前面先讨论递归到底的情况情况
        if root is None:
            return res

        if root.left is None and root.right is None:
            res.append(str(root.val))
            return res

        # 字符串列表
        left_paths = self.binaryTreePaths(root.left)
        for path in left_paths:
            res.append(str(root.val) + '->' + path)
        # 字符串列表
        right_paths = self.binaryTreePaths(root.right)
        for path in right_paths:
            res.append(str(root.val) + '->' + path)

        return res

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0257-binary-tree-paths ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。