《剑指offer》 第8题 二叉树的下一个节点

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

思路1：直接找节点。
1.如果这个节点A有右子树，就是这个节点A右子树的最小左子节点。也就是从A的右子树出发，一直向左找。
2.如果这个节点A没有右子树，那这个节点A的下一个节点就在A节点的父节点或祖父节点中。
 2.1 如果A是B的左子节点，那么B是A父节点，也是A的下一节点。从整体上看，对B进行中序遍历的时候，A是B的左子树的最后一个节点，也是唯一节点。
 2.2 由2.1分析得，此时A是其父节点B的右节点。此时继续需要向B的父节点找，直到A在其某个祖父节点C的左子树的时候，C就是A的下一节点，而此时，从整体上看，对c进行中序遍历的话，A是C的左子树遍历的最后一个节点。

/*
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;
        }
        if (pNode.right != null) {
            pNode = pNode.right;
            while(pNode.left!=null)
                pNode=pNode.left;
            return pNode;
        }
        while(pNode.next !=null){   //题目中给的next代表的就是父节点
            if(pNode==pNode.next.left)
                return pNode.next;
            pNode=pNode.next;
        }
        return null;
    }
}