题目描述
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的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 {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
ArrayList<ArrayList<Integer>> paths=new ArrayList<ArrayList<Integer>>();
if(root==null)return paths;
find(paths,new ArrayList<Integer>(),root,target);
return paths;
}
public void find(ArrayList<ArrayList<Integer>> paths,ArrayList<Integer> path,TreeNode root,int target){
path.add(root.val);
if(root.left==null&&root.right==null){
if(target==root.val){
paths.add(path);
}
return;
}
ArrayList<Integer> path2=new ArrayList<>();
path2.addAll(path);
if(root.left!=null)find(paths,path,root.left,target-root.val);
if(root.right!=null)find(paths,path2,root.right,target-root.val);
}
}
讲解一下解题思路:
假设有如下二叉树:
输入整数target为: 9
进入到find()方法中,首先第一步就将根结点的值加进来, 第一个if语句肯定是过不了的,然后到下面
new了一个path2(对于为什么要new一个path2,是因为当你path左孩子这条路径的时候,如果那条路径不能用了,递归回来之后,你在判断右孩子的时候,你继续用path这个你觉得里面的值还是你当前这个节点的list吗,它里面已经加入了它后面的值了,所有相当于在当前结点保存一份用于判断当前结点右孩子的时候用的list);
第一个if对其跟结点的左孩子群进行判断,进来之后把4当成跟结点,而且现在的target整数,应该是target-root.val;然后继续,进来之后又是进行if语句的判断,发现值还是不满足第一个if(说明还没有到叶子结点),进行深入到结点5,发现已经到了叶子结点也就是满足了第一个if的判断进入发现,值并不满足target==root.val,那就不是我们要找的路径,不加入到paths中,然后递归回来,递归根结点4的右孩子,结点3是叶子结点,进入if语判断发现target=root.val;(这里解释一下,target经历了什么:第一个target=9,第一次target=9-2=7,第二次target=7-4=3);所以发现该路径是我们所要的路径,加入到paths;
后面的递归是一样的,你们可以按照各个的思路递归继续判断,问题基本上完美解决.
总结一下:为什么我现在没自己去敲代码了,因为时间紧迫,被逼的!赶时间,所以没办法.
Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。
它的内容包括：
- 大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
- 原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
- 持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
- 覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
- 不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
- 宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
- 宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
- 宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw
目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：
想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询
同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】 即可免费领取。
