二叉树的下一个结点

思路

中序遍历顺序：左 根 右

共有三种情况，并且是循序渐进的。

1. 最简单的，当前节点有右子树，那么查找右子树的最左节点并返回就行；

   if(pNode.right!=null){
            TreeLinkNode leftest = pNode.right;
            while(leftest.left!=null)
                leftest=leftest.left;
            return leftest;
        }

2. 如果当前节点无右子树，并且当前节点是父节点的左子树，那么返回父节点即可；

        if(isLeft(pNode))
            return pNode.next;
   //isLeft函数为判断节点是否为父节点的左子树，实现如下：
   boolean isLeft(TreeLinkNode node){
        return node!=null&&node.next!=null&&node.next.left==node;
    }

3. 如果当前节点无右子树，且是父节点的右子树，那么下一个节点就是：当前节点所在的左子树的根。如图：
   

   TreeLinkNode node = pNode.next;
            if(node==null)
                return null;
            //不断向上查找父节点，并判断父节点是否位于左方
            while(node!=null&&!isLeft(node))
                node=node.next;
            //如果是位于左方，那么返回其根
            if(isLeft(node))
            return node.next;
            //否则就是找不到，即当前节点是在根的右子树中
            else return null;

   完整代码：

   public class Solution {
   
    boolean isLeft(TreeLinkNode node){
        return node!=null&&node.next!=null&&node.next.left==node;
    }
   
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode==null)
            return null;
        if(pNode.right!=null){
            TreeLinkNode leftest = pNode.right;
            while(leftest.left!=null)
                leftest=leftest.left;
            return leftest;
        }
        if(isLeft(pNode))
            return pNode.next;
        else{
            TreeLinkNode node = pNode.next;
            if(node==null)
                return null;
            while(node!=null&&!isLeft(node))
                node=node.next;
            if(isLeft(node))
            return node.next;
            else return null;
   
        }
    }
   }

   时间复杂度：O(n)
   空间复杂度：O(1)