首页 > 其他 > 详细

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

时间:2020-10-02 00:21:02      阅读:2      评论:0      收藏:0      [点我收藏+]

标签:统计   ont   sum   lin   根节点   right   

剑指 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)

 

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

标签:统计   ont   sum   lin   根节点   right   

原文:https://www.cnblogs.com/hi3254014978/p/13758411.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号