JZ57：二叉树的下一个结点

思路：

• 1.如果有右孩子，后继节点就是最左边的
• 2.如果没有右孩子，判断是否是父节点的左孩子，是的话，返回，不是继续往上找
• 3.找不到就是null

即：如果一个结点有右子树，就将它右子树上最左的结点返回，否则将当前结点的指针往上窜，当窜到它是它父结点的左结点时停止，此时那个父结点就是原结点的后继

/*
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==null){
            return pNode;
        }
        //如果一个结点有右子树，就将它右子树上最左的结点返回
        if(pNode.right!=null){
            pNode=pNode.right;
            while(pNode.left!=null){
                pNode=pNode.left;
            }
            return pNode;
        }
        //将当前结点的指针往上窜，当窜到它是它父结点的左结点时停止，此时那个父结点就是原结点的后继
        else{
            TreeLinkNode parent=pNode.next;
            while(parent!=null && parent.left!=pNode){
                pNode=parent;
                parent=parent.next;
            }
            return parent;
        }
    }
}