剑指offer57-二叉树的下一个节点

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

/*
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)
    {

    }
}

刚开始看这道题目没太看懂什么意思，然后才反应过来其实就是让我们求给定的这个节点的中序遍历的下一个节点值，这个求解其实不依赖于根节点，而是考察的是大家对于中序遍历的理解，可以分为以下几种情况进行求解：

• 如果该节点有右子树，那么在右子树上找到最左边的那个节点即是我们要找的值；

• 如果该节点无右子树，而他是父节点的左子树，那么他的下一个节点即是他的父节点

• 如果该节点无右子树，而他是父节点的右子树，那么应该寻找到祖先节点为其父节点的左子树的节点的父节点