[数据结构与算法]算法面试题-二叉树的后继节点

题目：

在二叉树中找到一个节点的后继节点(结构比普通二叉树结构多了一个指向父节点的指针)

分析：

1.正常情况下可以得到二叉树的中序遍历序列，节点在该序列中的下一个节点就是后继节点，但是该方法时间复杂度为O(N)
2.知道父节点的话就可以从结构上找到后继节点，假设某个节点到后继节点在结构上距离为K，时间复杂度就是O(K)
假设要找节点x的后继节点：
① x有右树时，后继节点就是右树的最左节点
② x无右树，需要判断其是否为其父节点的左孩子(在中序遍历中，x一定是y左子树上最后打印的节点)：
  - 是的话x的父节点1为x的后继节点(右图)
  - 不是的话判断x的父节点2是否是1的左孩子，依次类推，直到x的父辈节点1是节点y的左孩子，则y是x的后继节点(左图)
                  y                    y
                 /                    /
                1                    1
                 \                  /
                  2                x
                   \
                    x         

代码：

public class SuccessorNode {
    public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int data) {
            this.value = data;
        }
    }

    public static Node getSucessorNode(Node node) {
        if (node == null) {
            return node;
        }
        // 1. 当node有右树时，后继节点就是右树的最左节点
        if (node.right != null){
            return getLeftMost(node.right);
        // 2. 当node无右树时，根据②分析
        }else {
            Node parent = node.parent;
            // 当前节点是其父节点的右孩子
            while (parent != null && parent.left != node){
                node = parent;
                parent = node.parent;
            }
            // 执行到这步说明：
            // 1. node节点是整棵树的最右节点，则parent==null导致循环的跳出
            // 2. 循环中的node为其父节点的左孩子，则parent.left==node导致循环的跳出
            return parent;
        }

    }

    // 找树中的最左节点
    public static Node getLeftMost(Node node) {
        if (node == null) {
            return node;
        }
        while (node.left != null) {
            node = node.left;
        }

        return node;

    }
}