二叉树的下一个结点

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

此题分几种情况

设结点为node
1.如果node为空,则返回null
2.如果node有右子树,则该结点下一结点是右子树的最左结点
3.如果node没有右子树,那么向上查找直到根结点,如果存在当前结点是父结点的左孩子,那么这个结点就是node的父结点,如果一直到根都没有,那么说明这个结点是树的最右结点,返回null即可

代码

 public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if (pNode==null){//如果结点为空
            return null;
        }
         //节点的中序后继 ：右子树不为空时，其右子树中最左下方的节点
        if(pNode.right != null ){
            pNode = pNode.right;
            while(pNode.left != null){
                pNode = pNode.left;
            }
            return pNode;
        }
        TreeLinkNode node=pNode;
        while (node.next!=null){
            //若节点是其父节点的左孩子，则其后继就是该节点
            if (node.next.left==node){
                return node.next;
            }
            //若节点是其父节点的右孩子，则继续向上找,如果到根了也可以停止
            node=node.next;
        }
         
        return null;
    }