vlambda博客
学习文章列表

【剑指offer】二叉树中和为某一路径

This browser does not support music or audio playback. Please play it in Weixin or another browser.
晚上打了很久的球,回来之后已经是精疲力竭了。但是说好的至少日更半年,还是要风雨无阻坚持下去的。闲话少叙,直接开始正文吧。

剑指Offer链接

二叉树中和为某一路径:https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey


1、题目描述



2、解题思路


根据题目我们要注意几个关键信息。一是从根节点到最后的叶子节点,所以不用关心中途为零的情况。二是如果有多个路径,需要把这些路径全部返回。根据昨天看到的题解,用类似于二叉树前序的遍历的递归方式确实很简单。写完之后也尝试去用栈来实现,但是由于时间太晚,没有做出来,等之后空闲了再看看吧。


利用递归的方式非常好理解,只需要把目标值(target)的变化和最后把结果集中删除最后一位弄明白就没问题了。这里的target在每次递归过程中都是一份新的变量,它不是个固定的全局变量。就相当于如果在第二层有三个子节点,那在第二层会出现三个target变量。这里面也会涉及到Java是值传递还是引用传递的知识点。


相反的是结果集(list)却是独一份,它的动态变化规则是把单条二叉树走的路线都加入到集合中,如果路线走完的结果是0,则加入总集合中。但是无论最终的target为不为0,都需要把list中最后一个元素删除。其原因是代表这条路线已经结束,我需要去继续走上一节点对应的另一条线了。最后就是重复这种工作。代码如下:


import java.util.ArrayList;/**public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { private ArrayList<ArrayList<Integer>> lists = new ArrayList<>(); private ArrayList<Integer> list = new ArrayList<>(); public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { if (root == null) return lists; list.add(root.val); target -= root.val; if (target == 0 && root.left == null && root.right == null) { lists.add(new ArrayList<>(list)); } FindPath(root.left, target); FindPath(root.right, target); list.remove(list.size() - 1); return lists;
}}


3、结语


如果想提升自己精神上的忍耐力,可以去做些体育运动锻炼耐力,个人感觉体育不仅是体能的体现,也可以是意志力的支持。