《剑指offer第二版》题8：二叉树的下一个节点

题目：给定一棵二叉树和其中的一个节点，如何找出中序遍历顺序的下一个节点？树中的节点除了有两个分别指向左右子节点的指针以外，还有一个指向父节点的指针。

img1.png

注意：从父节点指向子节点的指针用实线表示，从子节点指向父节点的指针用虚线表示。

上图的二叉树的中序遍历序列是{d,b,h,e,i,a,f,c,g}。我们以这棵树为例进行分析。

解题思路：

1. 如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点。也就是说，从右子节点出发一直沿着指向左子节点的指针，我们就能找到它的下一个节点。

上图所示的树，节点b的下一个记得点是h，节点a的下一个节点是f节点。

2. 接着我们分析一个节点没有右子树的情形。如果一个节点是它父节点的左子节点，那么它的下一个节点就是它的父节点。

上图所示的树，节点d的下一个节点就是b，节点f的下一个节点就是c。

3. 如果一个节点既没有右子树，并且它还是它父节点的右子节点，这种情形就比较复杂。我们可以沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点。如果这样的节点存在，那么这个节点的父节点就是我们要找的下一个节点。这段话比较绕口，直接先看下面的例子，再回过头来看这段话就理解了。

上图所示的树，为了找到i节点的下一个节点，我们沿着指向父节点的指针向上遍历，先到达节点e。由于节点e是它父节点b的右子节点，我们继续向上遍历到达节点b。节点b是它父节点a的左子节点，因此节点b的父节点a就是i节点的下一个节点。

找出节点g的下一个节点步骤类似。我们先沿着指向父节点的指针到达节点c。由于c节点是它父节点a的右子节点，所以我们继续向上遍历到达a节点。由于a节点是根节点，他没有父节点，因此节点g没有下一个节点。

代码实现

节点数据结构

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

算法实现

public static BinaryTreeNode getNext(BinaryTreeNode node) {
    if (node == null) {
        return null;
    }
    //保存要查找的下一个节点
    BinaryTreeNode target = null;

    /**
     * 如果一个节点有右子树，那么它的下一个节点就是它的右子树中的左子节点。
     * 也就是说右子节点出发一直沿着指向左子节点的指针，
     * 我们就能找到它的下一个节点。
     */
    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;
        //如果父节点不为空，并且自节点不是父节点的左孩子
        while (target != null && target.left != cur) {
            cur = target;
            target = target.parent;
        }
        return target;
    }
    return null;
}

测试用例

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

输出结果

f
h
g
b
i
c
null
e
a

参考链接：

• 【剑指Offer学习】【面试题58：二叉树的下一个结点】