【剑指offer】问题8：二叉树的下一个节点

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

先上代码。

    /**
     * 中序遍历中的下一个节点
     * @param pNode
     * @return
     */
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        TreeLinkNode retNode =  null;
        // 如果此节点有右子树，那么下一个节点就是右子树的最左边节点
        if(pNode.right != null){
            TreeLinkNode tmpNode = pNode.right;
            while(tmpNode.left != null){
                tmpNode = tmpNode.left;
            }
            return tmpNode;
        }
        // 如果此节点没有右子树，且是其父节点的左子节点，那么下一个节点就是其父节点
        if(pNode.next != null && pNode == pNode.next.left)
            return pNode.next;
        // 如果此节点没有右子树，且是其父节点的右子节点，那么一直向上寻找，找到一个节点是其父节点的左子节点，那么这个节点的父节点就是下一个节点
        if(pNode.next != null && pNode == pNode.next.right){
            TreeLinkNode tmpNode = pNode.next;
            while(tmpNode.next != null &&  tmpNode == tmpNode.next.right) {
                tmpNode = tmpNode.next;
            }
            return tmpNode.next;
        }
        return retNode;
    }

分析过程如注释所示。该题目主要是考察对数的结构以及数的中序遍历结果的理解。中序遍历就是先遍历左子树，再遍历根节点，最后遍历右子树。既然是找下一个节点，那就不用管左子树了。就可以简单的分为有右子树和无右子树两种情况。有右子树的时候，按照中序遍历的概念，就要找到他右子树的最左下角的节点（其实就是左子节点的左子节点的左子节点....），返回既是。无右子树的时候就需要把它的父节点也考虑进来了。当它是父节点的左子节点时，由于它没有右子树，那么下一个节点一定是他的父节点；当它是父节点的右子节点时，稍微复杂一些，这时他的父节点肯定已经遍历完了，需要再往上找。如果遇到当前节点是父节点的右子节点的情况，就继续往上找，因为他的父节点肯定被遍历过了。这样知道碰到一个当前节点是其父节点的左子节点时，停止搜索，当前节点的父节点，就是下一个节点。用语言描述起来有一些绕，用画图的方式应该好理解一些。第三种情况多看几次就懂了。