题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
解法一：
最直接的想法是直接构造出二叉树的中序遍历，然后查看当前节点的下一个节点是什么。
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
ArrayList<TreeLinkNode> list = new ArrayList<TreeLinkNode>();
TreeLinkNode root = pNode;
//找到根节点，便于求中序遍历
while(root.next != null) {
root = root.next;
}
getInfix(root, list);
int i = 0;
//查找pNode在中序遍历中的位置
for(; i < list.size(); i++) {
if(list.get(i) == pNode) {
break;
}
}
//输出pNode的下一个节点
if(i + 1 < list.size()) {
return list.get(i + 1);
}
else {
return null;
}
}
//求中序遍历
public void getInfix(TreeLinkNode pNode, ArrayList<TreeLinkNode> list) {
if(pNode != null) {
getInfix(pNode.left, list);
list.add(pNode);
getInfix(pNode.right, list);
}
}
}
解法二：
但是很明显解法一要占用额外的空间，且当树很大的时候效率很低。
其实求下一个节点时，例如2的下一个节点，我们很容易便可以看出是3，而无需考虑整体的排序结果，那么有没有办法直接得到每个点的下一个节点呢？
我们可以将二叉树中的点进行分类，由于是中序遍历，一个点的下一个节点只可能出现在自己的上方或者右子树中，不可能出现在左子树中，我们可以将节点分为
1、含有右子树的节点
例如节点3。这种节点的下一个节点必定为右子树的最左边的节点。
2、不含有右子树的节点
（1）为父节点的左子节点。
例如节点2。这种节点的下一个节点必定为自己的父节点。
（2）为父节点的右子节点。
例如节点9。求这种节点的下一个节点，应一直往上找，直到找到一个点A，A是A.parent的左子节点，则所求的下一节点则为A.parent
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode == null) {
return pNode;
}
TreeLinkNode res = null;
//含有右子树的节点
if(pNode.right != null) {
pNode = pNode.right;
while(pNode.left != null) {
pNode = pNode.left;
}
res = pNode;
}
else {
//不含右子树且为父节点的左子节点
if(pNode.next != null && pNode.next.left == pNode) {
res = pNode.next;
}
else {
//不含右子树且为父节点的右子节点
while(pNode.next != null && pNode == pNode.next.right) {
pNode = pNode.next;
}
res = pNode.next;
}
}
return res;
}
}
