「力扣」第 257 题:二叉树的所有路径


「力扣」第 257 题:二叉树的所有路径

传送门:257. 二叉树的所有路径

给定一个二叉树,返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

1
/   \
2     3
\
5

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

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

要求:给定一棵二叉树,返回所有表示从根结点到叶子结点路径的字符串。

关键:理解“回溯”在深度优先搜索里面的应用。

思路1:使用递归完成,中途记录路径,走到叶子结点的时候结算;

Python 代码:特别注意:通过参数传递的方式,就没有显式的回溯的过程了

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# 257. 二叉树的所有路径
# 给定一个二叉树,返回所有从根结点到叶子结点的路径。


class Solution:

    # 深度优先遍历,我感觉最好理解
    # 参考:https://leetcode.com/problems/binary-tree-paths/discuss/68258/Accepted-Java-simple-solution-in-8-lines

    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:使用深度优先遍历,回溯的方式,一定要记住:一条路径走完以后,要弹出栈

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
        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()

以上两种方法都使用了辅助函数,其实还可以不借助辅助函数,直接在原来的函数上做递归。

LeetCode 第 257 题:二叉树的所有路径

Python 代码:

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 []

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

        left_paths = self.binaryTreePaths(root.left)
        for lpath in left_paths:
            res.append(str(root.val) + '->' + lpath)

        right_paths = self.binaryTreePaths(root.right)
        for rpath in right_paths:
            res.append(str(root.val) + '->' + rpath)

        return res

我写的题解地址:

# 参考:https://leetcode.com/problems/binary-tree-paths/discuss/68258/Accepted-Java-simple-solution-in-8-lines

LeetCode 第 257 题:二叉树的所有路径

给定一个二叉树,返回所有从根结点到叶子结点的路径。

Python 代码:使用递归完成,中途记录路径,走到叶子结点的时候结算; 特别注意:通过参数传递的方式,就没有显式的回溯的过程了。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def binaryTreePaths(self, root):
        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)

Python 代码:使用深度优先遍历,回溯的方式,一定要记住:一条路径走完以后,要弹出栈

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def binaryTreePaths(self, root):
        res = []
        if root is None:
            return res
        path = []
        self.__helper(root, path, res)
        return res

    def __helper(self, node, path, res):
        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
            # 因为 path 里的内容还要弹出
            # return
        if node.left:
            self.__helper(node.left, path, res)
        if node.right:
            self.__helper(node.right, path, res)
        path.pop()

LeetCode 第 257 题:得到二叉树的所有路径。

给定一个二叉树,返回所有从根节点到叶子节点的路径。

传送门:https://leetcode.com/problems/binary-tree-paths/description/

分析:典型的回溯。下面的这个写法比较奇怪。

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;
    }
}

心得:分析递归关系是这道题的难点。


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 104 题:求一棵二叉树的最大深度(简单) 「力扣」第 104 题:求一棵二叉树的最大深度(简单)
「力扣」第 297 题:二叉树的序列化与反序列化(困难)
下一篇 
「力扣」第 104 题:求一棵二叉树的最大深度(简单) 「力扣」第 104 题:求一棵二叉树的最大深度(简单)
「力扣」第 236 题:二叉树的最近公共祖先 中文网址:236. 二叉树的最近公共祖先 ; 英文网址:236. Lowest Common Ancestor of a Binary Tree , 给定一个二叉树, 找到该树中两个指定
  目录