問題：

求一個二叉樹中一個節(jié)點的后繼節(jié)點（后繼節(jié)點是中序遍歷后的集合每個元素的下一個元素）

思路：

后繼節(jié)點一共有兩種情況，一種情況是當前節(jié)點有右子樹，那么當前節(jié)點的后繼節(jié)點一定在它的右子樹上，即為右子樹的最左邊（這里的最左邊是指當前結(jié)點的右孩子以及之下它的右孩子之下的樹結(jié)構(gòu)的最左邊），比如下圖

image.png

第二種情況是，當前結(jié)點沒有右子樹，那么就依次網(wǎng)上找，找到一種情況是當前節(jié)點是它的父親節(jié)點的左孩子的時候，那么這個父親節(jié)點就是我原始節(jié)點的后繼節(jié)點

代碼：

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;
    }