【剑指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、结语
如果想提升自己精神上的忍耐力,可以去做些体育运动锻炼耐力,个人感觉体育不仅是体能的体现,也可以是意志力的支持。