面试题8:二叉树的下一个节点

    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode==null)return null;
        // 如果一个节点有右子树，则中序遍历中，他的下一个节点是右子树中最左端的节点
        if(pNode.right!=null){
            TreeLinkNode temp = pNode.right;
            while(temp!=null)
                if(temp.left!=null)
                    temp = temp.left;
                else
                    break;
            return temp;
        }
        // 节点没有右子树, 但左子树非空，下一个节点是自己的父节点
        else if(pNode.left!=null){
            return pNode.next;
        }
        // 节点左右子树都空, 如果当前是左孩子节点，下一个是父节点
        // 如果当前是右孩子节点，下一个要向上找，直到某个节点是左孩子，返回那个节点的父节点
        // 如果一直找到了跟节点还是右孩子，则没有下一个节点，
        // 如果找到跟节点时是左孩子，则根是下一个节点
        else{
            if(pNode.next==null) return null;//左右子树都空，父节点也空，是只有一个跟的树
            // 当前是左孩子
            if(pNode.next.left==pNode)
                return pNode.next;
            // 当前是右孩子
            else{
                TreeLinkNode ind = pNode.next;
                boolean flag = false;
                // 一直向上找,找到根的亲儿子
                while(ind.next!=null){
                    // 他不是左孩子
                    if(ind.next.left!=ind)
                            ind = ind.next;
                    else
                    {flag=true;break;}
                }
                // 找到了一个左孩子
                if(flag){
                    return ind.next;
                }
                else{
                   return null;
                }
            }
            
        }
    }