关键词：
问题描述
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历中的下一个结点并且返回
要求
时间限制:1秒 空间限制:32768K
方法原型
public TreeNode getNext(TreeNode treeNode)
public class TreeNode
int val;
TreeNode left = null;
TreeNode right = null;
TreeNode parent = null;
TreeNode(int val) this.val = val;
分析思路
二叉树的中序遍历对学习过数据结构的人都不陌生，即先递归访问当前树节点的左子树，再访问当前节点，然后递归访问右子树。
比如对于二叉树：
其中序遍历的结果为：
4, 2, 8, 5, 9, 1, 6, 3, 7
对于任意一个节点，要找到其中序遍历中的下一个节点，我们可以分情况讨论，一共三种情况：
- 当前节点有右子树：如上图中的1，3，2，5
- 当前节点没有右子树，且是父节点的左孩子：如上图中的4，6，8
- 当前节点没有右子树，且是父节点的右孩子：如上图中的9，7
对于这三种，找出它们下一个节点的方法分别是：
当前节点有右子树
下一个节点是该右子树中的最左元素。
如上图中的1的下一个节点是6，相关的伪代码为：
If(node.right != null)
node = node.right;
while(node.left != null)
node = node.left;
next = node
当前节点没有右子树，且是父节点的左孩子
父节点就是下一个节点。如下图中的元素4，其下一个节点是2.
相关的伪代码如下：
if(node.parent != null && node.parent.left == node)
next = node.parent
当前节点没有右子树，且是父节点的右孩子
这种情况下，需要往根回溯，如果遇到某个节点是作为左孩子存在，则那个节点的父节点就是我们要找的下一个元素。
如图中的9号元素，从它开始往根回溯，当遇到2时，2是作为1的左孩子存在，那么1就是我们要找寻的“下一个”元素。
以下动图体现找寻过程：
当然，也可能存在我们直到遍历到根也没有发现作为左孩子存在的元素，那说明当前节点已经是最后一个，没有下一个节点存在。
相关伪代码如下：
while(node.parent != null)
node = node.parent;
if(node = node.parent.left)
next = node.parent;
return;
相关代码
以上思路的JAVA版本实现如下：
package com.shellmad;
public class Solution
public static void main(String[] args)
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);
TreeNode node9 = new TreeNode(9);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node5.left = node8;
node5.right = node9;
node3.left = node6;
node3.right = node7;
node2.parent = node1;
node3.parent = node1;
node4.parent = node2;
node5.parent = node2;
node8.parent = node5;
node9.parent = node5;
node6.parent = node3;
node7.parent = node3;
Solution solution = new Solution();
TreeNode node = null;
node = solution.getNext(node1);
if (node != null)
System.out.println(node.val);
else
System.out.println("没有下一个节点");
node = solution.getNext(node2);
if (node != null)
System.out.println(node.val);
else
System.out.println("没有下一个节点");
node = solution.getNext(node3);
if (node != null)
System.out.println(node.val);
else
System.out.println("没有下一个节点");
node = solution.getNext(node4);
if (node != null)
System.out.println(node.val);
else
System.out.println("没有下一个节点");
node = solution.getNext(node5);
if (node != null)
System.out.println(node.val);
else
System.out.println("没有下一个节点");
node = solution.getNext(node6);
if (node != null)
System.out.println(node.val);
else
System.out.println("没有下一个节点");
node = solution.getNext(node7);
if (node != null)
System.out.println(node.val);
else
System.out.println("没有下一个节点");
node = solution.getNext(node8);
if (node != null)
System.out.println(node.val);
else
System.out.println("没有下一个节点");
node = solution.getNext(node9);
if (node != null)
System.out.println(node.val);
else
System.out.println("没有下一个节点");
public TreeNode getNext(TreeNode treeNode)
// 检查节点是否为空
if (treeNode == null)
return null;
// 处理情况1,当前节点有右子树
if (treeNode.right != null)
treeNode = treeNode.right;
while (treeNode.left != null)
treeNode = treeNode.left;
return treeNode;
// 处理情况2和3
while (treeNode.parent != null)
if (treeNode == treeNode.parent.left)
return treeNode.parent;
treeNode = treeNode.parent;
return null;
class TreeNode
int val;
TreeNode left = null;
TreeNode right = null;
TreeNode parent = null;
TreeNode(int val)
this.val = val;
面试题8：二叉树的下一个节点(代码片段)
一.题目给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针。二.思路分析题目之后，我们发现，待处理节点只存在三种... 查看详情
剑指offer（57）二叉树的下一个节点(代码片段)
题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 题目分析这题一定要画图，因为只有画图我们才能分清楚下一... 查看详情
59.二叉树的下一个节点(代码片段)
题目描述：??给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。思路分析：??二叉树的下一个节点，一共有以下情况：??1.二叉... 查看详情
二叉树的遍历算法(代码片段)
...据结构，遍历算法作为一个基础的算法，两者结合当然是经典的组合了。很多题目都会有ta的身影，有直接问二叉树的遍历的，有间接问的。比如要你找到树中满足条件的节点，就是间接考察树的遍历，因为你要找到树中满足条... 查看详情
二叉树的下一个节点(代码片段)
题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 1/*2publicclassTreeLinkNode3intval;4TreeLinkNodeleft=null;5TreeLinkNoderight=null... 查看详情
二叉树的下一个节点(代码片段)
题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。思路首先知道中序遍历的规则是：左根右，然后作图 1.若当前... 查看详情
[剑指offer]面试题8：二叉树的下一个节点(代码片段)
题目描述 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 解题思路 1.找到所有的可能情况并归纳，写的代码需... 查看详情
11道精选经典leetcode例题让你彻底搞懂二叉树的广度优先遍历(代码片段)
...要求，也会成为我们解题的关键，今天我们用11道经典LeetCode算法题认识二叉树的广度优先搜索有上述二叉树，我们利用队列Queue对其进行层序遍历先使6提前进入队列6进队列第1轮遍历，6出队列，6的两个子节点... 查看详情
二叉树的下一个结点(代码片段)
...语言2秒空间限制：C/C++32M，其他语言64M题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。思路：中序遍历：左中右，... 查看详情
剑指offer——06二叉树的下一个节点(代码片段)
题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 题目的意思是，在一颗二叉树的中序遍历中，给出其中一个节... 查看详情
剑指offer：二叉树的下一个节点(代码片段)
题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。classTreeLinkNode:def__init__(self,x):self.val=xself.left=Noneself.right=Noneself.paren... 查看详情
剑指offer（书）：二叉树的下一个节点(代码片段)
题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。分析：若一个节点有右子树，那么他的下一个节点就是他右子树中的... 查看详情
算法题之求二叉树的最大距离
二叉树是一种非常经典的数据结构。如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。下面我们随意构... 查看详情
剑指offer-二叉树的下一个节点(代码片段)
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 ①节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着... 查看详情
剑指offer(python)------二叉树的下一个节点(代码片段)
题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。这道题意即：给定一个节点，按照中序遍历（左根右）的方式求该... 查看详情
⭐算法入门⭐《二叉树》简单04——leetcode104.二叉树的最大深度(代码片段)
文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目1、题目描述 给定一个二叉树，找出其最大深度。二叉树的深度为根节点到... 查看详情
⭐算法入门⭐《二叉树》简单05——leetcode111.二叉树的最小深度(代码片段)
文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目1、题目描述 给定一个二叉树，找出其最小深度。二叉树的深度为根节点到... 查看详情
数据结构二叉树经典入门算法题集锦（下）(代码片段)
前言：本章将通过五道来自LeetCode/牛客网中的二叉树相关算法题来介绍数据结构中二叉树在算法题中的应用，题目难度不大，大家就当放松放松。文章目录1.二叉树的最大深度思路分析：题解：2.平衡二叉树思... 查看详情