后继节点：中序遍历的后一个节点
普通二叉树：中序遍历得到一个list，时间复杂度O(n)
本题的二叉树：有父节点的指针，后继节点与原节点的距离为1，因此可以直接通过父节点找到下一个节点
优化：节点到另一个节点的真实距离为k，时间复杂度为O(k)
情况分析：
情况一：节点node有右子树，后继节点为右子树上的最左节点
情况二：节点node无右子树，沿着node向上找第一个作为左孩子的祖先，左孩子的父节点就是node的后继节点（因为此时节点node为节点Y左子树最右侧的节点）
对于情况二，在找到节点Y之后，节点Y即为node的后继节点，节点Y有没有右子树不重要
情况三：节点node本身为整颗二叉树最右的节点，没有后继节点，返回null
文章来源：https://www.toymoban.com/news/detail-721403.html
package binarytree;
public class SuccessorNode {
public class Node {
int value;
Node left;
Node right;
Node father;//这里定头节点的father节点为null，在创建二叉树时需要注意
public Node(int data) {
this.value = data;
}
}
public Node getsuccessorNode(Node node) {
if (node == null) {
return node;
}
if (node.right != null) {//节点node有右子树
while (node.left != null) {//找到最左的节点
node = node.left;
}
return node;//返回右子树的最左节点
} else {//没有右子树，向上找
//node不为父节点的左孩子 并且 node的父节点不为null 则向上找
while (node != node.father.left && node.father != null) {
node = node.father;//此时为第一个不为右孩子的节点；此时为第一个为左孩子的节点
}
node = node.father;
//如果node不是整颗二叉树的最右的节点，返回左孩子的父节点
//如果node是整颗二叉树的最右的节点，node一直找到头节点，头节点的father为null，返回null
return node;
}
}
}
文章来源地址https://www.toymoban.com/news/detail-721403.html
到了这里，关于寻找二叉树一个节点的后继节点的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
