首页 > 试题广场 >

二叉树的下一个结点

[编程题]二叉树的下一个结点

热度指数：466025 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

示例:

输入:{8,6,10,5,7,9,11},8

返回:9

解析:这个组装传入的子树根节点，其实就是整颗树，中序遍历{5,6,7,8,9,10,11}，根节点8的下一个节点就是9，应该返回{9,10,11}，后台只打印子树的下一个节点，所以只会打印9，如下图，其实都有指向左右孩子的指针，还有指向父节点的指针，下图没有画出来

数据范围：节点数满足 $1 \le n \le 50 \$ ，节点上的值满足 $1 \le val \le 100 \$

要求：空间复杂度 $O(1) \$ ，时间复杂度 $O(n)\$

输入描述:

输入分为2段，第一段是整体的二叉树，第二段是给定二叉树节点的值，后台会将这2个参数组装为一个二叉树局部的子树传入到函数GetNext里面，用户得到的输入只有一个子树根节点

输出描述:

返回传入的子树根节点的下一个节点，后台会打印输出这个节点

示例1

输入

{8,6,10,5,7,9,11},8

输出

示例2

输入

{8,6,10,5,7,9,11},6

输出

示例3

输入

{1,2,#,#,3,#,4},4

输出

示例4

输入

{5},5

输出

"null"

说明

不存在，后台打印"null"

说明：本题目包含复杂数据结构TreeLinkNode，点此查看相关信息

算法知识视频讲解

牛客题解官

发表于 2020-06-02 11:21:56

精华题解题目的主要信息：题目给出我们一棵树的其中的某一个结点指针我们需要返回这棵树按照中序遍历的该节点的下一个顺序结点指针树的每个节点都有三个指针，指向左子节点、右子节点、父节点举一反三：学习完本题的思路你可以解决如下题目： JZ54. 二叉搜索树的第k个节点 JZ68. 二叉搜索树的最近公共展开全文

Maokt

发表于 2021-07-09 15:24:02

精华题解算法思想一：暴力法解题思路：直接模拟题意。题意需要找到某个结点中序遍历的下一个结点，那很显然可以这样： 1、根据给出的结点求出整棵树的根节点 2、根据根节点递归求出树的中序遍历，存入res中 3、在res中查找当前结点，则当前结点的下一结点即为所求。 1、当找到当前结点是数组最展开全文

牛客786963925号

发表于 2021-07-07 23:02:07

精华题解解法一：暴力解法据题意，「某结点的下一个结点」定义为「中序遍历」后的下一个结点。因此暴力解法的步骤为：根据输入的结点以及next指针，先求得二叉树的根结点root；利用root进行二叉树的中序遍历，并定义数组储存中序遍历的结果；遍历该数组，得到「下一个结点」。注意：二叉树的中序遍历步骤展开全文

江南好___

发表于 2021-07-06 20:23:32

精华题解描述题目描述给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。输入描述：输入分为2段，第一段是整体的二叉树，第二段是给定二叉树节点的值，后台会将这2个参数组装为一个二叉树局部的子树传入到函数GetNex 展开全文

叫我皮卡丘

发表于 2019-08-09 19:28:32

【剑指offer】二叉树的下一个结点 --Java实现 1. 还原二叉树 1. 分析既然给了二叉树的某个结点，且二叉树存储着指向父结点的指针（next），那我们可以先找到根节点，再对树进行中序遍历，最后根据中序遍历结果找到给定结点的下一结点 2. 代码 import java.util.*; pu 展开全文

初憶

发表于 2019-08-13 01:20:30

二叉树的下一个结点：根据中序遍历的规则，当结点存在右子树的时候，中序遍历的下一个结点为右子树的最左节点。但是当节点不存在右子树的时候，中序遍历的下一个结点必定为该节点的父辈节点。但是究竟是哪一辈呢？根据中序遍历特性，左父结点一定已经被中序遍历访问过，所以下一个结点一定是在父节点路径上的第一个右父展开全文

一叶浮尘

发表于 2020-03-02 13:19:33

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 /* public class TreeLinkNode { int val; TreeLinkNode left = null; Tre 展开全文

sk8niki

发表于 2020-02-01 20:25:26

先画一个二叉树： Java方式实现找到一个二叉树中序遍历的下一个节点思路：😃 如果一个节点有右子树的时候，那么它的下一个节点就是它的右子树中的最左子节点。（比如说b的下一个节点是h，可以试着画一个二叉树）😗 如果一个节点没有展开全文

橙子爱吃桃子

发表于 2020-04-23 23:07:00

C++/代码： class Solution { public: TreeLinkNode* GetNext(TreeLinkNode* pNode) { if(pNode->right) { pNode = pNode->righ 展开全文

宫水三叶的刷题日记

发表于 2021-07-03 14:27:39

朴素解法一个朴素的做法是，根据题目对于 TreeLinkNode 的定义，利用 next 属性存储「当前节点的父节点」这一特点。从入参节点 pNode 出发，不断利用 next 属性往上查找，直到找到整棵树的头节点，令头节点为 root。然后实现二叉树的「中序遍历」，将遍历过程中访问的节点存放展开全文