题目
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。题目地址
我感觉可以自己先做做，你说呢！！！！！！
解题思路
先看一个颗二叉树
典型二叉树
中序遍历的顺序是左中右，这颗树的中序遍历是ACBDFHEMG
观察可得到，所给结点如果
- 有右子树，那么他的下一个节点就是先找右子树，再向下一直找左子树。例如C结点，他的下一个点是B，也就是先找右子树D，再一直找左子树，找到B。
- 没有右子树，那么就需要往父节点方向找，怎么找，可以先想想看。。。。。。 答案：找到一个所在枝干是左子树为之
举个栗子🌰
没有右子树可能不好理解，我们看下上面的树。D和G都没有右子树，D的下一个节点是F，而G没有下一个结点。可以看出一直往父节点寻找，找到一个所在枝干是左子树为之。例如B没有右子树，向上找，找到D，在D的左子树上，命中，下一个就是D。G没有右子树，向上找，找到E，在右子树，继续找，找到F，还在右子树，无法向上了，说明不存在下一个结点。D没有右子树，向上找，找到C，在右子树，继续找，找到F，在左子树，命中，返回F。
代码
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode.right != null){
//有右子树，先右，再一直左
pNode = pNode.right;
while(pNode.left != null){
pNode = pNode.left;
}
return pNode;
} else {
//没有右子树，向上找树枝所在左侧的结点
while(pNode.next != null){
if(pNode.next.left == pNode){return pNode.next;}
pNode = pNode.next;
}
}
return null;
}
}
