一、题目
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
二、思路
结合图，我们可发现分成两大类：
1、有右子树的，那么下个结点就是右子树最左边的点；（eg：D，B，E，A，C，G）
2、没有右子树的，也可以分成两类：
a)是父节点左孩子（eg：N，I，L） ，那么父节点就是下一个节点 ；
b)是父节点的右孩子（eg：H，J，K，M）找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置。如果没有（eg：M），那么他就是尾节点。
三、代码
/*
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 pNode;
} // 节点有右子树,那么下个结点就是右子树最左边的点
if (pNode.right != null) {
pNode = pNode.right;
while (pNode.left != null) {
pNode = pNode.left;
}
return pNode;
// 节点无右子树且该节点为父节点的左子节点,那么父节点就是下一个节点
} else if (pNode.next != null && pNode.next.left == pNode) {
return pNode.next;
// 节点无右子树且该节点为父节点的右子节点,找该节点的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置
} else if (pNode.next != null && pNode.next.right == pNode) {
while (pNode.next != null && pNode.next.left != pNode) {
pNode = pNode.next;
}
return pNode.next;
//如果该节点的父节点的父节点的父节点...，找不到满足条件(当前结点是其父节点的左孩子位置)的节点，则该节点为尾节点，返回空
} else {
return pNode.next;//找不到满足条件的节点，pNode已经为根节点了，返回pNode.next,即返回空，也可以直接写 return null;
}
}
}
---------------------------------------------
参考链接：
https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e