网站站外链接网站首页推广

后继节点：中序遍历的后一个节点

普通二叉树：中序遍历得到一个list，时间复杂度O(n)

本题的二叉树：有父节点的指针，后继节点与原节点的距离为1，因此可以直接通过父节点找到下一个节点

优化：节点到另一个节点的真实距离为k，时间复杂度为O(k)

情况分析：

情况一：节点node有右子树，后继节点为右子树上的最左节点

情况二：节点node无右子树，沿着node向上找第一个作为左孩子的祖先，左孩子的父节点就是node的后继节点（因为此时节点node为节点Y左子树最右侧的节点）

        对于情况二，在找到节点Y之后，节点Y即为node的后继节点，节点Y有没有右子树不重要

情况三：节点node本身为整颗二叉树最右的节点，没有后继节点，返回null

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，返回nullreturn node;}}}