leetcode 剑指 Offer 34. 二叉树中和为某一值的路径

剑指 Offer 34. 二叉树中和为某一值的路径

题目描述

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

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

返回:

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

提示：

节点总数 <= 10000

思路：

其实是统计根节点到每个叶子结点的值是否等于给定值。不能用当前和大于sum来进行剪枝，因为接下来的结点可能还有负数

 1 class Solution {
 2     public List<List<Integer>> pathSum(TreeNode root, int sum) {
 3         List<List<Integer>> res = new ArrayList<>();
 4         LinkedList<Integer> temp = new LinkedList<>();
 5         preOrder(root, 0, sum, temp, res);
 6         return res;
 7     }
 8     // 借助一个辅助函数，遍历树，同时统计路径和，前序递归遍历
 9     public void preOrder(TreeNode root, int nowSum, int sum, LinkedList<Integer> temp, List<List<Integer>> res){
10         if(root != null){
11             temp.addLast(root.val);
12             nowSum += root.val;
13             // 必须是叶子结点才能算是有效组合
14             if(root.left == null && root.right == null && nowSum == sum){
15                 res.add(new LinkedList<Integer>(temp));
16             }
17             // 如果不是叶子结点且当前和加上当前结点的值小于等于sum, 递归统计左右子树
18             preOrder(root.left, nowSum, sum, temp, res);
19             preOrder(root.right, nowSum, sum, temp, res);
20             temp.removeLast();  // 回溯消除影响
21         }
22     }
23 }

leetcode运行时间为2ms, 空间为39.5MB

复杂度分析：

时间复杂度：对每个结点都进行了一次遍历，所以时间复杂度为O(n)

空间复杂度：空间复杂度取决于栈的深度，而栈的深度又取决于树的高度，树的高度最低为O(logn), 最高为O(n), 所以空间复杂度的最好和最坏情况分别为O(logn)和O(n)