題目：給定一棵二叉樹(shù)和其中的一個(gè)節(jié)點(diǎn)，如何找出中序遍歷順序的下一個(gè)節(jié)點(diǎn)？樹(shù)中的節(jié)點(diǎn)除了有兩個(gè)分別指向左右子節(jié)點(diǎn)的指針以外，還有一個(gè)指向父節(jié)點(diǎn)的指針。

img1.png

注意：從父節(jié)點(diǎn)指向子節(jié)點(diǎn)的指針用實(shí)線表示，從子節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針用虛線表示。

上圖的二叉樹(shù)的中序遍歷序列是{d,b,h,e,i,a,f,c,g}。我們以這棵樹(shù)為例進(jìn)行分析。

解題思路：

1. 如果一個(gè)節(jié)點(diǎn)有右子樹(shù)，那么它的下一個(gè)節(jié)點(diǎn)就是它的右子樹(shù)中的最左子節(jié)點(diǎn)。也就是說(shuō)，從右子節(jié)點(diǎn)出發(fā)一直沿著指向左子節(jié)點(diǎn)的指針，我們就能找到它的下一個(gè)節(jié)點(diǎn)。

上圖所示的樹(shù)，節(jié)點(diǎn)b的下一個(gè)記得點(diǎn)是h，節(jié)點(diǎn)a的下一個(gè)節(jié)點(diǎn)是f節(jié)點(diǎn)。

2. 接著我們分析一個(gè)節(jié)點(diǎn)沒(méi)有右子樹(shù)的情形。如果一個(gè)節(jié)點(diǎn)是它父節(jié)點(diǎn)的左子節(jié)點(diǎn)，那么它的下一個(gè)節(jié)點(diǎn)就是它的父節(jié)點(diǎn)。

上圖所示的樹(shù)，節(jié)點(diǎn)d的下一個(gè)節(jié)點(diǎn)就是b，節(jié)點(diǎn)f的下一個(gè)節(jié)點(diǎn)就是c。

3. 如果一個(gè)節(jié)點(diǎn)既沒(méi)有右子樹(shù)，并且它還是它父節(jié)點(diǎn)的右子節(jié)點(diǎn)，這種情形就比較復(fù)雜。我們可以沿著指向父節(jié)點(diǎn)的指針一直向上遍歷，直到找到一個(gè)是它父節(jié)點(diǎn)的左子節(jié)點(diǎn)的節(jié)點(diǎn)。如果這樣的節(jié)點(diǎn)存在，那么這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)就是我們要找的下一個(gè)節(jié)點(diǎn)。這段話比較繞口，直接先看下面的例子，再回過(guò)頭來(lái)看這段話就理解了。

上圖所示的樹(shù)，為了找到i節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，我們沿著指向父節(jié)點(diǎn)的指針向上遍歷，先到達(dá)節(jié)點(diǎn)e。由于節(jié)點(diǎn)e是它父節(jié)點(diǎn)b的右子節(jié)點(diǎn)，我們繼續(xù)向上遍歷到達(dá)節(jié)點(diǎn)b。節(jié)點(diǎn)b是它父節(jié)點(diǎn)a的左子節(jié)點(diǎn)，因此節(jié)點(diǎn)b的父節(jié)點(diǎn)a就是i節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。

找出節(jié)點(diǎn)g的下一個(gè)節(jié)點(diǎn)步驟類(lèi)似。我們先沿著指向父節(jié)點(diǎn)的指針到達(dá)節(jié)點(diǎn)c。由于c節(jié)點(diǎn)是它父節(jié)點(diǎn)a的右子節(jié)點(diǎn)，所以我們繼續(xù)向上遍歷到達(dá)a節(jié)點(diǎn)。由于a節(jié)點(diǎn)是根節(jié)點(diǎn)，他沒(méi)有父節(jié)點(diǎn)，因此節(jié)點(diǎn)g沒(méi)有下一個(gè)節(jié)點(diǎn)。

代碼實(shí)現(xiàn)

節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)

private static class BinaryTreeNode {
    private char val;
    private BinaryTreeNode left;
    private BinaryTreeNode right;
    private BinaryTreeNode parent;

    public BinaryTreeNode() {
    }

    public BinaryTreeNode(char val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return val + "";
    }
}

算法實(shí)現(xiàn)

public static BinaryTreeNode getNext(BinaryTreeNode node) {
    if (node == null) {
        return null;
    }
    //保存要查找的下一個(gè)節(jié)點(diǎn)
    BinaryTreeNode target = null;

    /**
     * 如果一個(gè)節(jié)點(diǎn)有右子樹(shù)，那么它的下一個(gè)節(jié)點(diǎn)就是它的右子樹(shù)中的左子節(jié)點(diǎn)。
     * 也就是說(shuō)右子節(jié)點(diǎn)出發(fā)一直沿著指向左子節(jié)點(diǎn)的指針，
     * 我們就能找到它的下一個(gè)節(jié)點(diǎn)。
     */
    if (node.right != null) {
        target = node.right;
        while (target.left != null) {
           target = target.left;
        }
        return target;
    } else if (node.parent != null) {
        target = node.parent;
        BinaryTreeNode cur = node;
        //如果父節(jié)點(diǎn)不為空，并且自節(jié)點(diǎn)不是父節(jié)點(diǎn)的左孩子
        while (target != null && target.left != cur) {
            cur = target;
            target = target.parent;
        }
        return target;
    }
    return null;
}

測(cè)試用例

private static void assemble(BinaryTreeNode node, BinaryTreeNode left, BinaryTreeNode right, BinaryTreeNode parent) {
    node.left = left;
    node.right = right;
    node.parent = parent;
     }

     public static void test00() {
        BinaryTreeNode n1 = new BinaryTreeNode('a');
        BinaryTreeNode n2 = new BinaryTreeNode('b');
        BinaryTreeNode n3 = new BinaryTreeNode('c');

        BinaryTreeNode n4 = new BinaryTreeNode('d');
        BinaryTreeNode n5 = new BinaryTreeNode('e');
        BinaryTreeNode n6 = new BinaryTreeNode('f');

        BinaryTreeNode n7 = new BinaryTreeNode('g');
        BinaryTreeNode n8 = new BinaryTreeNode('h');
        BinaryTreeNode n9 = new BinaryTreeNode('i');

        assemble(n1, n2, n3, null);
        assemble(n2, n4, n5, n1);
        assemble(n3, n6, n7, n1);
        assemble(n4, null, null, n2);
        assemble(n5, n8, n9, n2);
        assemble(n6, null, null, n3);
        assemble(n7, null, null, n3);
        assemble(n8, null, null, n5);
        assemble(n9, null, null, n5);

        System.out.println(getNext(n1));
        System.out.println(getNext(n2));
        System.out.println(getNext(n3));
        System.out.println(getNext(n4));
        System.out.println(getNext(n5));
        System.out.println(getNext(n6));
        System.out.println(getNext(n7));
        System.out.println(getNext(n8));
        System.out.println(getNext(n9));
    }

輸出結(jié)果

f
h
g
b
i
c
null
e
a

參考鏈接：

• 【劍指Offer學(xué)習(xí)】【面試題58：二叉樹(shù)的下一個(gè)結(jié)點(diǎn)】