后继节点

问题：

求一个二叉树中一个节点的后继节点（后继节点是中序遍历后的集合每个元素的下一个元素）

思路：

后继节点一共有两种情况，一种情况是当前节点有右子树，那么当前节点的后继节点一定在它的右子树上，即为右子树的最左边（这里的最左边是指当前结点的右孩子以及之下它的右孩子之下的树结构的最左边），比如下图

image.png

第二种情况是，当前结点没有右子树，那么就依次网上找，找到一种情况是当前节点是它的父亲节点的左孩子的时候，那么这个父亲节点就是我原始节点的后继节点

代码：

public static Node getNextNode(Node node) {
        if (node == null) {
            return node;
        }
        if (node.right != null) {
            return getLeftMost(node.right);
        } else {
            Node parent = node.parent;
            while (parent != null && parent.left != node) {
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }

    public static Node getLeftMost(Node node) {
        if (node == null) {
            return node;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }