首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如何使用递归返回从树根到目标的树节点的ArrayList?

使用递归返回从树根到目标的树节点的ArrayList的方法如下:

  1. 首先,我们需要定义一个树节点的数据结构,包含节点值和指向子节点的指针。
  2. 创建一个空的ArrayList来存储结果。
  3. 编写递归函数,该函数接受当前节点和目标节点作为参数。
  4. 在递归函数中,首先检查当前节点是否为空。如果为空,则返回空的ArrayList。
  5. 然后,检查当前节点是否为目标节点。如果是,则创建一个只包含当前节点值的ArrayList,并返回。
  6. 如果当前节点不是目标节点,则递归调用函数来搜索当前节点的子节点。
  7. 将子节点返回的ArrayList添加到当前节点的值之前,并返回新的ArrayList。
  8. 在主函数中,调用递归函数,并将树的根节点和目标节点作为参数传递。

下面是一个示例代码:

代码语言:txt
复制
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class TreeTraversal {
    public static ArrayList<Integer> findPath(TreeNode root, TreeNode target) {
        ArrayList<Integer> path = new ArrayList<>();
        if (root == null) {
            return path;
        }
        
        if (root == target) {
            path.add(root.val);
            return path;
        }
        
        ArrayList<Integer> leftPath = findPath(root.left, target);
        if (!leftPath.isEmpty()) {
            path.addAll(leftPath);
            path.add(root.val);
            return path;
        }
        
        ArrayList<Integer> rightPath = findPath(root.right, target);
        if (!rightPath.isEmpty()) {
            path.addAll(rightPath);
            path.add(root.val);
            return path;
        }
        
        return path;
    }
    
    public static void main(String[] args) {
        // 创建一个示例树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        
        // 查找从根节点到目标节点5的路径
        TreeNode target = root.left.right;
        ArrayList<Integer> path = findPath(root, target);
        
        // 输出路径
        for (int i = path.size() - 1; i >= 0; i--) {
            System.out.print(path.get(i) + " ");
        }
    }
}

这个例子中,我们创建了一个包含7个节点的二叉树。然后,我们使用递归函数findPath来查找从根节点到目标节点5的路径。最后,我们按照从根节点到目标节点的顺序输出路径节点的值。输出结果为:1 2 5。

腾讯云相关产品和产品介绍链接地址:

  • 腾讯云云服务器(CVM):提供弹性、安全、稳定的云服务器实例,适用于各类应用场景。
  • 腾讯云云数据库 MySQL 版:提供高性能、可扩展的云数据库服务,适用于存储和管理大规模数据。
  • 腾讯云对象存储(COS):提供安全、可靠、低成本的云端对象存储服务,适用于存储和管理各类文件和数据。
  • 腾讯云人工智能:提供丰富的人工智能服务和工具,包括图像识别、语音识别、自然语言处理等,适用于各类人工智能应用开发。
  • 腾讯云物联网(IoT):提供全面的物联网解决方案,包括设备接入、数据管理、应用开发等,适用于物联网应用开发和管理。
  • 腾讯云移动开发:提供一站式移动应用开发服务,包括移动应用开发平台、移动测试服务等,适用于移动应用开发和测试。
  • 腾讯云区块链:提供安全、高效的区块链服务和解决方案,适用于各类区块链应用开发和管理。
  • 腾讯云元宇宙:提供虚拟现实(VR)和增强现实(AR)技术和平台,适用于虚拟现实和增强现实应用开发和体验。

请注意,以上只是腾讯云的一些相关产品,还有其他云计算品牌商也提供类似的产品和服务。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

【剑指 の 精选】详解「二叉中序遍历下一个结点」两种解法

示例: 输入:{8,6,10,5,7,9,11},8 返回:9 解析:这个组装传入树根节点,其实就是整颗,中序遍历{5,6,7,8,9,10,11},根节点8下一个节点就是9,应该返回{9,10,11...输入描述:输入分为2段,第一段是整体二叉,第二段是给定二叉树节点值,后台会将这2个参数组装为一个二叉局部子树传入函数GetNext里面,用户得到输入只有一个子树根节点。...返回值描述:返回传入树根节点下一个节点,后台会打印输出这个节点。...= null) root = root.next; // 对进行一遍「中序遍历」,保存结果 list 中 dfs(root); // list...「中序遍历」遍历顺序为为 「左-根-右」 可知,其父节点已经被遍历过了,我们需要递归找到符合 node.equals(node.next.left) 节点作为答案返回,如果没有则说明当前节点是整颗二叉最靠右节点

63820

【数据结构初阶】链式二叉接口实现+痛苦OJ题

return 0; } 3.二叉树前、中、后序遍历(递归神圣大门开启) 我们先确定一下递归单层逻辑,逻辑很简单,如果是前序遍历,我们就输出根结点,左子树根节点,右子树根节点值,以这样逻辑方式递归遍历整个二叉...对于单层逻辑的话也是比较简单,我们将问题拆为,只拿根节点data和x比较看是否相等,相等我们立马返回,不相等就拿左子树根节点data和x比较,如果还不相等,我们就继续拿右子树根节点data和x...3.当我们计算好左子树和右子树高度之后,我们用一个三运算符来进行二叉深度返回。...//1.就是如果我左边中找到我右边了,那就递归结束了 //2.或者来root以及root左和右子树中找了半天,NULL了都还没找到,那递归也应该结束了 5.二叉遍历(注意下标 i 参数设计...) 二叉遍历 这道题其实最大难点就是,我们如何通过前序遍历方式来递归创建一棵二叉,至于后面的中序遍历二叉,输出二叉内容,那就是个小配菜,所以我们把重心放在如何去先序遍历字符串然后递归建立一棵二叉树上

25520
  • 【数据挖掘】决策算法简介 ( 决策模型 | 模型示例 | 决策算法性能要求 | 递归创建决策 | 树根属性选择 )

    决策模型过程 : ① 训练过程 : 使用训练集数据确定决策时使用属性 , 确定根节点 , 内部节点 , 叶子节点 属性划分 , 训练决策模型 ; ② 预测过程 : 节点特征开始 , 根据决策判定序列依次节点向下判定...决策 属性划分 : 属性划分策略 : 根据一定策略 , 确定哪个属性作为树根 , 然后每个子树 , 在确定剩余哪个属性作为子树树根 , 这是递归问题 ; 属性划分算法性质 : 递归算法 ; 如何决定树根属性...决策模型创建 : 决策模型创建核心就是选择合适树根 , 将重要属性放在树根 , 然后子树中 , 继续选择子树中重要属性放在子树树根 , 依次递归 , 最终得到决策结果 ( 叶子节点 ) ;...决策创建算法 ( 递归 ) : 使用递归算法 , 递归算法分为递归操作 和 递归停止条件 ; 3 ....递归操作 : 每个步骤先选择属性 , 选择好属性后 , 根据 总 ( 子树 ) 树根属性划分训练集 ; ① 选择属性 : 递归由上到下决定每一个节点属性 , 依次递归构造决策 ; ② 数据集划分

    74330

    二叉八股文:递归改迭代通用模板

    而且我们前文 学习数据结构和算法框架思维 特别强调过,练习递归框架思维最好方式就是二叉相关题目开始刷,前文也有好几篇手把手带你刷二叉和二叉搜索文章: 手把手带你刷二叉(第一期) 手把手带你刷二叉...前文 BFS 算法框架详解 是利用队列迭代地遍历二叉,不过使用是层级遍历,没有递归遍历中前中后序之分。 由于现在面试越来越卷,很多读者在后台问我如何将前中后序递归框架改写成迭代形式。...递归框架改为迭代 参加过我二叉专项训练读者应该知道,二叉递归框架中,前中后序遍历位置就是几个特殊时间点: 前序遍历位置代码,会在刚遍历当前节点root,遍历root左右子树之前执行;...我们递归遍历二叉函数也是一样,当函数被调用时,被压入调用栈,当函数结束时,调用栈中弹出。...迭代解法这里就搞定了,不过我还是想强调,除了 BFS 层级遍历之外,二叉题目还是用递归方式来做,因为递归是最符合二叉树结构特点

    40230

    【剑指 の 精选】宏观角度看「对称二叉」问题

    Tag : 「剑指 Offer」、「二叉」、「层序遍历」、「迭代」、「递归」 描述: 请实现一个函数,用来判断一棵二叉是不是对称。...因此,如果我们使用常规遍历方式进行检查的话,需要对空节点有所表示。...一个朴素做法是:使用「层序遍历」方式进行「逐层检查」,对于空节点使用 emptyNode 进行代指,同时确保不递归 emptyNode 对应节点。...当且仅当两棵子树符合如下要求时,满足 “对称” 要求: 两棵子树根节点值相同; 两颗子树左右子树分别对称,包括: a 左子树与 b 右子树相应位置值相等 a 右子树与 b 左子树相应位置值相等...当我们整体层面出发考虑时,配合递归,往往能写出比常规做法要简洁得多代码。 建议大家加深对「局部」和「整体」两种不同出发点理解。

    31040

    如何遍历文件夹下上亿文件而不栈溢出

    序:一个文件夹下面有很多层小文件,如何算出这个文件夹下面有多少文件?...当时我灵光一闪,因为当时我在温故数据结构知识,我说这个文件夹层次看着好呀嘛好眼熟,不就相当于一个结构,那我们学数据结构时候是如何遍历节点。...有左递归,中递归,右递归,当然这就是上面的递归方法,不是我们要找解决方案,那么该怎么办? 看,角落里有我们经常忽视层序遍历。...层序遍历:层序遍历就是所在节点出发,首先访问第一层树根节点,然后从左到右访问第2层上节点,接着是第三层节点,以此类推,自上而下,自左至右逐层访问结点过程就是层序遍历。...代码思路: 我们只需要使用一个list集合来存储每一个文件(夹),然后按次序读取list集合元素,并判断如果是文件夹则把该文件夹下所有文件(夹)追加到list集合后面,然后读取list下一个元素以此类推

    59130

    如何遍历文件夹下上亿文件而不栈溢出

    序:一个文件夹下面有很多层小文件,如何算出这个文件夹下面有多少文件?...当时我灵光一闪,因为当时我在温故数据结构知识,我说这个文件夹层次看着好呀嘛好眼熟,不就相当于一个结构,那我们学数据结构时候是如何遍历节点。...有左递归,中递归,右递归,当然这就是上面的递归方法,不是我们要找解决方案,那么该怎么办? 看,角落里有我们经常忽视层序遍历。...层序遍历:层序遍历就是所在节点出发,首先访问第一层树根节点,然后从左到右访问第2层上节点,接着是第三层节点,以此类推,自上而下,自左至右逐层访问结点过程就是层序遍历。...代码思路: 我们只需要使用一个list集合来存储每一个文件(夹),然后按次序读取list集合元素,并判断如果是文件夹则把该文件夹下所有文件(夹)追加到list集合后面,然后读取list下一个元素以此类推

    1K20

    二叉基础及实现(二,加经典OJ)

    判断一颗二叉是否是平衡二叉: 题目: 方法一:时间复杂度为O(N^2,N平方);因为我们求高度自己实现函数getHeight,是先遍历,最后一个二叉再逐一返回,当(isBalanced(root.left...,右边会返回-1,会破坏右边二叉返回高度 所以,rightTreeHeight值要判断;如果等于-1,就不可以向上返回 限制:(rightTreeHeight>...root = new TreeNode(preorder[preIndex]); //在中序遍历中,前序遍历那里找到,代表所有子树节点 int rootIndex...root = new TreeNode(postorder[postorIndex]); //在中序遍历中,前序遍历那里找到,代表所有子树节点 int rootIndex...二叉后序非递归遍历实现: 这里思路也是大同小异,但是这里要定义一个,prev引用,记录一下被打印过节点,左右cur就不会一直在,top右边死循环了 图解: 代码: public List

    8010

    从前序与中序遍历序列构造二叉

    前序遍历数组第 1个数(索引为0)数一定是二叉根结点,于是可以在中序遍历中找这个根结点索引,然后把“前序遍历数组”和“中序遍历数组”分为两个部分,就分别对应二叉左子树和右子树,分别递归完成就可以了...下面是一个具体例子,演示了如何计算数组子区间边界: 建议看完本题可以再看一下中序和后序遍历构造二叉 leetcode 106....从中序与后序遍历序列构造二叉 方法一:在递归方法中,传入数组拷贝(不推荐、复杂度较高) class Solution { public: TreeNode* buildTree(vector...inorder.begin()+pos+1, inorder.begin() +inorder.size()); root->right = buildTree(p2, i2); //返回当前二叉节点...return root; } }; 方法二:在递归方法中,传入子数组边界下标 边界下标的计算,大家可以参考一开始展示计算边界图片 class Solution { public

    33320

    算法:二叉遍历类题目

    在任意一个非空中:(1)每个元素称为结点(node);(2)仅有一个特定结点被称为根结点或树根(root)。...可见(tree)定义本身就是迭代递归定义。 二叉节点度不大于2有序,它是一种最简单且最重要。 1....level).add(root.val); // 当前节点访问完之后,再使用递归方式分别访问当前节点左右子节点 levelHelper(res, root.left, level +...基于递归应用问题 由定义可知,定义是递归,所以可以通过递归去解决一些类问题。使用递归解决问题一般有两种思路:1. 自顶向下。2. 自底向上。...如果题目可以在当前任意节点就可以判断出返回结果,则适合使用自顶向下(增加剪枝效果)。如果题目必须遍历叶子节点后才能计算出中间值,则需要使用自底向上。

    24330

    java优先级队列(基于堆)

    二叉堆存储结构 二叉堆是一颗完全二叉,基于数组存储(元素都是靠左排列,数组中存储时不会浪费空间) 只有完全二叉适合使用数组这种结构来存储, 其他二叉都要用链式结构 2.1.2 关于节点值...堆中根节点值 >= 子树节点值(最大堆,大根堆) 堆中根节点值 <=子树中节点值(最小堆,小根堆) 节点层次和节点大小没有任何关系,只能保证当前中,树根是最大值。...交换 最后52上浮最大位置 上浮操作终止条件: 当前已经上浮树根 =》 这个元素一定是最大值 当前元素 <= 父节点对应元素值,此时元素落到在正确位置 2.2.2 在堆中取出最大值(shiftDown...步骤如下: 最大堆最大值一定处在树根节点,直接取出树根即可 需要融合左右两个子树,使得取出树根后这棵仍然是最大堆 将堆中最后一个元素顶到堆顶,然后进行元素下沉操作。...不断将子树调整为最大堆时,最终走到树根时,左右子树已经全部是最大堆,只需最后下沉根节点就能最终最大堆。

    71030

    【数据结构】二叉链式结构实现

    设二叉根结点所在层数为1 ,层序遍历就是所在二叉根结点出发,首先访问第一层树根结点,然后从左到右访问第 2 层上结点,接着是第三层结点,以此类推,自上而下,自左至右逐层访问结点过程就是层序遍历...二叉遍历与构建都清楚了,那我们如何用代码统计二叉节点个数,我们想想如果二叉节点为空,那么个数就返回0,若不为空,就是自身节点算一个,左孩子节点个数加右孩子节点个数加1(自身),那么对于子问题也是如此求个数...K行节点个数,不返回最后一行叶子结点个数,返回任意一行节点个数 假如我返回第三行节点个数,那在我们遍历过程中,我们如何确定节点是否是第三行那,我们有图可以过一行K减一,只要向下递归一行K减一,目标行第三行...二叉深度,就是通过比较左右子树深度高那个加一,不断递归,找到最高深度,代码如下 这里我们要注意一下,如图第一个代码,三操作符你会发现大那位会多调用一次,若递归越深,效率会急速下降,所以我们可以将他们值用临时变量来判断...5.寻找x节点 这个首先通过先序遍历遍历每个节点,找到的话返回这个节点,若没找到,返回NULL,扎到的话用临时变量接收,不能直接返回,以为在递归遍历中,你返回返回递归过程中上一个函数,并不能完全返回出来

    8110

    『LeetCode』#1刷题日记

    二叉最大深度 ✅ 题意 给你一个二叉根结点root,判断该深度(层数) 思路 递归 class Solution { public int maxDepth(TreeNode root...// 递归思路 // root左子树 根节点为root.left 右子树根节点为root.right // 找左右子树层数最大值...+1 (1为根节点层数) // 在各个子树递归过程中,最后一层(left==null right==null 0+1=1)返回上一层、层层加一 } }...验证二叉搜索 ✅ 题意 给你一个二叉节点 root ,判断其是否是一个有效二叉搜索 二叉搜索定义: 节点左子树只包含 小于 当前节点数。...✅ 题意 判断给定二叉是否轴对称 思路 // 对于每一层 左子树根节点val == 右子树根节点val // 同时 左子树左孩子等于右子树右孩子 左子树右孩子等于右子树左孩子 class

    17740

    二叉查找

    一个二叉查找就是一个二叉,每个节点上包含有一个键一个值一个指向左节点链接一个指向右节点链接(这个图中数字代表键,值没有显示)。...一个二叉必须有一个根节点,我们首先查找这个元素是否在根节点里,如果在,ok返回就可以了;如果不在,所查找元素key大于rootkey,就去右子树中查找,小于就去左子树中查找,任何子树都有一个根,我们就可以继续这个过程...可以看到不论是查找还是插入我们都在对数级别实现了对应操作,也都使用递归操作,递归实现优点是简单易懂一了然,但同样,非递归实现效率要更高一些,而且jvm是对栈深有限制,如果递归过深,stackoverflow...删除最小结点 因为二叉查找是有序,结点左子树键总是小于这个结点键,于是节点开始我们不断查找结点左子树结点,一旦一个结点左子树为空,那么这个结点就是键最小结点。...(t.right)返回是t右子树删除最小结点之后节点,所以这一步也就是用x来代替t位置 将x左链接设为t.left,然后通过递归调用返回更新各个链接,x对t替代全部完成 public void

    51520

    【一天一大 lee】二叉后序遍历 (难度:中等) - Day20200929

    题目: 给定一个二叉返回 后序 遍历。...抛砖引玉 深度优先遍历(DFS) 二叉后续遍历:先遍历左子树,在遍历右子树,最后遍历子树根节点 思路 先用“很简单”递归算法解决下吧 /** * Definition for a binary...node.right) _result.push(node.val) } dfs(root) return _result } 广度优先遍历(BFS) 迭代,先处理左右子树再处理子树根节点...== 'root') { queue.push(node) queue.push('root') // 先处理左右子树再处理子树根节点,注意处理顺序是数组尾部开始所有先存又自身再存左子树...queue.push(node.right) if (node.left) queue.push(node.left) } else { // 遇到root则说明其前一个节点是子树根节点

    62120

    二叉链式结构

    前序遍历思想和打印结果 思路:root结点为1结点,向下走,1左孩子节点为2,再向下走,2结点,2结点左孩子为4,向下走,4结点,4结点左孩子为空,此时左孩子空节点函数栈帧销毁,返回结点...结点进入,返回值是1+left(结点数)+right(右节点数),首先先递归到4,左右指数都是0,此时值就是1,返回到结点2......  ...* root);  代码实现: 思路:刚开始进入结点1,向下运行代码,递归值用一个整数接收, 用一个三操作符,哪个子树值大,就返回哪个结点值加1,1表示这个结点。...,递归,当找到结点时, 根据代码返回该结点,返回节点定义 find ,然后继续运行代码,继续返回该  find ,直到递推到结点1,然后就得到该结点了。...设二叉根结点所在层数为1,层序遍历就是所在二叉根结点出发,首先访问第⼀层树根结点,然后从左到右访问第2层上结点,接着是第三层结点,以此类推,自上而下,自左至右逐层访问结点过程就是层序遍历

    8410

    二叉就这么简单

    节点连接起来就成了,而节点由一个数据、两个指针组成 因此,创建树实际上就是创建节点,然后连接节点 首先,使用Java类定义节点: public class TreeNode { // 左节点...如果访问有孩子节点,先处理孩子,随后返回 无论先中后遍历,每个节点遍历如果访问有孩子节点,先处理孩子(逻辑是一样) 因此我们很容易想到递归 递归出口就是:当没有子节点了,就返回 因此,我们可以写出这样中序遍历代码...,右边树根去 tempRoot = tempRoot.getRightNode(); }...三、查询二叉查找相关 3.1查询深度 查询深度我们可以这样想:左边子树和右边字数比,谁大就返回谁,那么再接上根节点+1就可以了 ?...查找深度、查找最大值都用到了递归递归在非线性数据结构中是用得非常多应用也非常广泛,此篇简单地说明了数据结构,高级东西我也没弄懂,可能以后用到时候会继续深入…

    1.1K80

    PAT 1020 Tree Traversals (25分) 解读

    第四步,右子树HMZ有三个节点,根G往左移三个位置后D必然是它左子树根。 第五步,观察发现,上面的过程是递归。...该步递归过程可以简洁表达如下: 1 确定根,确定左子树,确定右子树。 2 在左子树中递归。 3 在右子树中递归。 4 返回或者打印当前根。...但是因为 我们序列是数组,下标是0开始,所以为了避免 2 * 0 = 0节点值覆盖,我们左孩子编号是 2*i+1,右孩子编号是 2*i+2,当然你可以选择让根节点编号是1,就不会有这个问题。...inorder数组中结束位置 * post_index 当前子树树根在 postorder数组中下标 * * 我们在递归时,每次找到都是当前树根,然后分别去它左右子树递归 * 所以我们增加参数...> in_end) return; int i = in_start; // post_end总是表示当前子树树根在整棵后序遍历数组中下标 // 找到当前子树树根在中序遍历序列中位置

    49930

    【硬核】机器学习与数据结构完美结合——KD-tree

    有些小伙伴表示喜欢看这些硬核,于是今天上点硬菜,我们来看一个机器学习领域经常用到数据结构——KD-Tree。 线段KD 在讲KD之前,我们先来了解一下线段概念。...从下图当中我们不难看出来,这棵线段维护是一个区间内最大值。比如树根是8,维护是整个区间最大值,每一个中间节点值都是以它为树根子树中所有元素最大值。...如果我们把空间看成是广义区间,那么它和线段原理是一样。最后得到也是一棵完美二叉,因为我们每次都选择了数据集中点进行划分,可以保证树根叶子节点长度不会超过。...也就是说我们树根开始,选择第0维作为排序和切分数据依据,然后到了深为1这一层,我们选择第一维,深为2这一层,我们选择第二维,以此类推。当深超过了K时候,我们就对深取模。...这个时候我们需要判断,整棵当中搜索是否已经结束,如果当前节点已经是根节点了,说明我们遍历结束了,那么返回候选集,否则说明还没有,我们需要继续搜索。

    85230
    领券