面试题8(剑指offer)--二叉树的下一个节点

题目：

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

思路：

1. 如果当前节点有右孩子节点，如果其右孩子有左孩子节点，则其右孩子的最左孩子节点就是当前节点的下一个节点，如果其右孩子节点没有左孩子节点，则右孩子节点就是当前节点的下一个节点。
2. 如果当前节点没有右孩子，但有父节点，如果当前节点是其父节点的右孩子，则pNode=pNode.next(next就是父指针)，直到是左孩子或者next为空，如果是左孩子，它的下一个节点就是他的父节点，如果next为空，则其下一个节点为空。

代码：

    private static TreeLinkNode nextNode(TreeLinkNode pNode) {
        if (pNode==null){
            return null;
        }
        if (pNode.right!=null){
            TreeLinkNode rightChild=pNode.right;
            while (rightChild.left!=null){
                rightChild=rightChild.left;
            }
            return rightChild;
        }else if (pNode.next!=null){
            while (pNode.next!=null&&pNode.next.right==pNode){
                pNode=pNode.next;
            }
            if (pNode.next==null){
                return null;
            }
            return pNode.next;
        }
        return null;
    }