[剑指offer][Java]二叉树的下一个节点

题目

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

程序核心思想

如果这个节点的右孩子不为空，那么它的下一个节点一定在它的右子树上，所以再检查它的右子树，返回它右子树的最左的节点（如果有的话），否则返回右子树的根节点。
如果这个节点的右孩子为空，那么检查它是否是它父节点的右节点，如果不是（那就是它父节点的左节点），那么返回它的父节点；如果是（它父节点的右节点），那么返回让它指向它的父节点，再次做同样的检查（是否是它父节点的右节点），直到他的父节点为空，那么意为着题目给出的这个节点是整棵树的最右的节点，则返回null。

Tips

在做pNode == pNode.next.right这种一个指针后面还有指针的操作时，要保证第一个不为空指针，方法可以是pNode.next != null && pNode == pNode.next.right。

代码

/*
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 null;
        
        while(true){
            if(pNode.right != null){
                pNode = pNode.right;
                while(pNode.left != null){
                    pNode = pNode.left;
                }
                return pNode;
            }else{
                while(pNode.next != null  && pNode == pNode.next.right){
                    pNode = pNode.next;
                }
                if(pNode.next == null || pNode.next == pNode){
                    return null;
                }
                return pNode.next;
            }
        }
    }
}