二叉树的下一个节点

思路如下图：

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null; //指向左
    TreeLinkNode right = null;//指向右
    TreeLinkNode next = null;//指向父亲

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode.right != null){
            //第一种情况，当右节点不为空
            TreeLinkNode t = pNode.right;
            while(t.left!=null){
                t = t.left;
            }
            return t;
        }else{
            TreeLinkNode t = pNode.next; //获取当前节点的父亲节点
            if(t == null){
                //当当前节点是根节点，且无右节点时，这时候的父亲节点是null，那么当前节点是最后一个节点，返回null
                return null;
            }
            if(t.left == pNode){
                //第二种情况：当前节点是父亲节点的左孩子
                return t;
            }else{
                boolean flag = false;
                while(t.next != null){
                    if(t.next.left == t){
                        flag = true;
                        break;
                    }
                    t = t.next;
                }
                //第三种情况：当前节点是父亲节点的右孩子
                if(flag == true){
                    return t.next;
                }else{
                    return null;
                }

            }
        }
    }
}