题目
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
分析
借用网上的一个图片：
我们按照当前节点是否含有右子树进行分类分析：
-思考一 如果当前节点有右子树，那么按照中序遍历“左-根-右”的顺序，我们只要找到当前节点右子树的最左节点就是下一个节点。
-思考二 如果当前节点没有右子树，又要分两种情况。
（1）当前节点是其父节点的左孩子，那么下一个节点就是其父节点。
（2）当前节点是其父节点的右还在，就要找到其父亲的父亲的父亲。。。。。。直到当前节点是其父亲的左孩子。
代码
/*
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;
}
// 如果当前节点没有右孩子，有两类情况
// (1) 当前节点是父节点的左孩子，那么下一个节点就是父节点
// (2) 当前孩子是父节点的右孩子，那么就要知道他父节点的父节点的父节点。。。。。
//直到当前节点是父节点的左孩子
while(pNode.next != null){
if (pNode.next.left == pNode) {
return pNode.next;
}
pNode = pNode.next;
}
return null;
}
}
