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

分析

对于一棵如下的二叉树，其中序遍历为 {d, b, h, e, i, a, f, c, g}。

1
2
3
4
5
6
7

         a
       /   \
      b     c
     / \   / \
    d   e f   g
       / \
      h   i

有如下的规律：

  1. 如果给定的节点有右子树，则该节点在中序遍历中的下一个节点就是其右子树中最左侧的节点。例如，给定节点为 b，则 b 的下一个节点就是以 e 为根节点的子树的最左边的节点，即 h。同样的 a 的下一个节点就是 f；

  2. 如果给定的节点没有右子树，则需要判断其与父节点的关系：

　　2.1) 如果给定的节点是其父节点的左节点，则给定的节点的下一节点就是其父节点。例如，d->b，f->c；

　　2.2) 如果给定的节点是其父节点的右节点，则可以沿着该节点的父指针向上找，直到找到一个是它父节点的左子节点的节点，找到则返回该节点，找不到则说明给定的节点没有下一节点，返回 null。

例如，给定节点 i 没有右子树，朝上找到 e 不满足条件，再找到 b，由于 a 的左节点是 b，所以 i 的下一节点就是 a 了。而对于 g 来说，向上找到 c 不满足条件，然后再找到 a 还是不满足条件，则说明 g 没有下一节点。

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public class NextNodeInBinaryTrees {
    public static TreeNode getNextNode(TreeNode node){
        if(node == null) return null;
        else if(node.right != null){
            node = node.right;
            while(node.left != null){
                node = node.left;
            }
            return node;
        }

        while (node.parent != null){
            if(node.parent.left == node) return node.parent;
            node = node.parent;
        }
        return null;
    }
}

详解

第 4~9 行就对应上面讲到的第 1) 条，而第 12~14 行对应的就是第 2 条。