LCOF 34. 二叉树中和为某一值的路径

最后更新于4年前

这有帮助吗？

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例: 给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

[
   [5,4,11,2],
   [5,8,4,5]
]

提示：

节点总数 <= 10000

2. 解法

2.1 Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 结果列表
    LinkedList<List<Integer>> res = new LinkedList<>();
    // 路径
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recursion(root, sum);
        return res;
    }

    public void recursion(TreeNode root, int sum) {
        // 判空
        if (root == null)
            return;

        // 首先把根结点加入到路径中
        path.add(root.val);
        // 路径和减去根结点的值
        sum -= root.val;

        // 此时需要判断一下路径和是否等于 0 且根结点不存在左右结点，若成立，把此时的路径添加到结果中
        if (sum == 0 && root.left == null & root.right == null)
            res.add(new LinkedList(path));

        // 递归左右子树
        recursion(root.left, sum);
        recursion(root.right, sum);

        // 回溯，删去此时路径中的最后一个结点
        path.removeLast();
    }
}

2.2 Kotlin

pending

2.3 复杂度分析

时间复杂度 O(N)：N 为二叉树的结点数，先序遍历需要遍历所有结点。

空间复杂度 O(N)：最差情况下，即当树退化为链表时，path 需要存储所有结点，占用 O(N) 额外空间。

LCOF 34. 二叉树中和为某一值的路径

LCOF 34. 二叉树中和为某一值的路径

1.

2. 解法

2.1 Java

2.2 Kotlin

2.3 复杂度分析

3. 参考

4. 标签

1.

2. 解法

2.1 Java

2.2 Kotlin

2.3 复杂度分析

3. 参考

4. 标签