下面给大家分享的是找二叉树的下一个节点的代码实现和思路，感兴趣的朋友可以进来了解一下，具体包含了3种思路代码实现方式。
题目：
指定一个二叉树和其中的一个结点，找出中序遍历顺序的下一个结点并返回。
注：树中的结点不仅仅包括了左右子结点，还包括了指向父结点的指针。
思路1：
首先我们要了解中序遍历的规则：左根右，之后作图。
结合上面的图，大致可以分成2类：
1、有右子树的，则下一个结点就是右子树最左边的点;(eg：D，B，E，A，C，G)
2、没有右子树的，大致也可以分成2类
a)是父节点左孩子(eg：N，I，L) ，则父节点就是下一个节点;
b)是父节点的右孩子(eg：H，J，K，M)找他的父节点的父节点的父节点，直到当前结点是其父节点的左孩子位置。
假如没有eg：M，则他就是尾节点。
代码实现：
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
*/
//分析二叉树的下一个节点，一共有以下情况：
//1.二叉树为空，则返回空；
//2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；
//3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。
classSolution
{
public: TreeLinkNode * GetNext(TreeLinkNode * pNode)
{
if (pNode == NULL)
returnNULL;
if (pNode - > right != NULL)
{
pNode = pNode - > right;
while (pNode - > left != NULL)
pNode = pNode - > left;
returnpNode;
}
while (pNode - > next != NULL)
{
TreeLinkNode * proot = pNode - > next;
if (proot - > left == pNode)
returnproot;
pNode = pNode - > next;
}
returnNULL;
}
};这个思路是非常清晰清楚的哦!
思路2：
代码实现：
public class Solution
{
TreeLinkNode GetNext(TreeLinkNode node)
{
if (node == null) return null;
if (node.right != null)
{ //如果有右子树，则找右子树的最左节点
node = node.right;
while (node.left != null) node = node.left;
return node;
}
while (node.next != null)
{ //没右子树，则找第一个当前节点是父节点左孩子的节点
if (node.next.left == node) return node.next;
node = node.next;
}
return null; //退到了根节点仍没找到，则返回null
}
}思路3：
1、假如，这个节点存在右子树，那么下一个节点为右子树最左子节点(如图节点B)
2、假如，这个节点不存在右子树。那么，这个时候就可以具体的分成两种情况：
(1)这个节点为父节点的左子节点，那么下一个节点为其父节点(如图节点D)
(2)这个节点为父节点的右子节点，那么沿着父节点向上遍历，直到找到一个节点的父节点的左子节点为该节点，那么该节点的父节点下一个节点(如图节点I，沿着父节点一直向上查找找到B(B为其父节点的左子节点)，那么B的父节点A为下一个节点)。
代码实现：
public class Solution
{
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if (pNode == null)
return pNode;
if (pNode.right != null)
{ // 节点有右子树
pNode = pNode.right;
while (pNode.left != null)
{
pNode = pNode.left;
}
return pNode;
}
else if (pNode.next != null && pNode.next.left == pNode)
{ // 节点无右子树且该节点为父节点的左子节点
return pNode.next;
}
else if (pNode.next != null && pNode.next.right == pNode)
{ // 节点无右子树且该节点为父节点的右子节点
while (pNode.next != null && pNode.next.left != pNode)
{
pNode = pNode.next;
}
return pNode.next;
}
else
{
return pNode.next; //节点无父节点 ，即节点为根节点
}
}
}以上就是3种关于找出二叉树的下一个节点的代码实现和思路了，想了解更多的相关内容，可以继续的关注本站的Java实例专栏了解。