二叉树的下一个结点-根据中序遍历的特点（O(n),O(1)）解题

//解题思路
/*
       8
    6    10
   5 7  9  11
根据中序遍历的特点（O(n),O(1)）：
1.pNode的右孩子为空，中序遍历顺序的下一个结点可能在其父辈root里（注意是父辈，不只是父亲）
    1.1 pNode为root的左孩子，则pNode的下一个结点为root（例如5、7、9）
    1.2 否则返回null（例如11）
2.pNode的右孩子不为空时，中序遍历顺序的下一个结点在其右子树里，此时中序遍历右子树取第一个结果即可（例如6、8、10）
 */
//犯错点
/*
  求中序遍历右子树取第一个结果即取右子树最左边的节点，不用调用inOrder()耗费运行时间
 */
public TreeLinkNode GetNext(TreeLinkNode pNode) {
    if (pNode == null) return null;
    //1.pNode的右孩子为空,中序遍历顺序的下一个结点可能在其父辈里
    if (pNode.right == null){
        TreeLinkNode root = pNode.next;
        TreeLinkNode child = pNode;
        //1.1 pNode为root父辈的左孩子，则pNode的下一个结点为root
        while (root != null){
            if (root.left == child) return root;
            child = root;
            root = root.next;
        }
        //1.2 父辈root为空，则返回null
        return null;
    }
    //2.pNode的右孩子不为空,中序遍历顺序的下一个结点在其右子树里，此时中序遍历右子树取第一个结果即可
    TreeLinkNode rightTree = pNode.right;
    //求中序遍历右子树取第一个结果即取右子树最左边的节点
    while (rightTree.left != null){
        rightTree = rightTree.left;
    }
    return rightTree;
}