面试题8：二叉树中序遍历的下一个节点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路：二叉树中序遍历的下一个节点一般分为三种情况：
1.如果当前节点存在右子树，则中序遍历的下一个节点为右子树或者右子树的最左子节点。
2.如果当前节点不存在右子树，并且其是父节点的左子树，则中序遍历的下一个节点是父节点
3.入股当前节点既不存在左子树，并且其是父节点的右子树，则中序遍历的下一个节点是向上遍历到是它父子节点的左子树的节点。
代码如下：

private class TreeLinkNode{
        int val;
        TreeLinkNode left;
        TreeLinkNode right;
        TreeLinkNode next;
        public TreeLinkNode(int val){
            this.val = val;
        }
    }
public TreeLinkNode GetNext1(TreeLinkNode pNode) {
         //如果当前节点存在右子节点，则中序下一个节点为右子树最左下的节点，如果右子树没有左子结点就返回右子树根结点
        if (pNode.right != null){
            pNode = pNode.right;
            while (pNode.left != null){
                pNode = pNode.left;
            }
            return pNode;
        }

        //如果不存在右子节点，则回到父节点中判断，如果父节点的右子树为该节点，则继续寻找父节点
        while (pNode.next != null && pNode == pNode.next.right){
            pNode = pNode.next;
        }
        //若该节点为父节点的左孩子，则下一个中序节点就是父节点

        return pNode.next;
    }