题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
解题思路分析
这道题如果能够很清楚的理解题意的话，其实不难做出的
首先，中序遍历下的下一个节点，那其实如果能够直接得到中序遍历之后的序列，是不是就可以直接拿到指定节点的下一个节点，但是啊，这个题目并没有给我们这颗二叉树的根节点，所有得到中序遍历的序列就变得不现实了，但其实并不影响。
中序遍历的下一个节点，咱们思考下，其实如果该节点有右孩子A的话，是不应该是该节点右子树中的最左的那个节点，或就是该节点的右孩子A
如果节点没有右孩子的话，那它的下一个节点肯定会在他的祖先节点，如果该节点是其父节点B的左孩子，那该节点的下一个节点就是其父节点B，如果是其右孩子的话，那么其实我们就是要一直顺着其祖先节点找下去，直到找到一个该节点的一个祖先节点C是这个祖先节点的父节点D的左孩子，然后这个父节点D就是我们要找的那个节点(有点绕，但是理解一下其实就很简单)
代码实现
public TreeLinkNode getInNext(TreeLinkNode pNode) {
if (pNode == null) {
return null;
}
//如果有右孩子，找到最左边的那个返回
if (pNode.right != null) {
return left(pNode.right);
}
//没有右孩子，开始顺着祖先节点往上找
TreeLinkNode father = pNode.parent;
//只要其父节点A一直是A的父节点的右孩子，就一直找下去
while (father != null && pNode = father.right) {
pNode = father;
father = father.patent;
}
//直到找到一个左孩子的情况，就返回回来
return father;
}
public TreeLinkNode left(TreeLinkNode node) {
if (node.left == null) {
return node;
}
return left(node.left);
}
