二叉树的下一个结点

2018-05-11

编程练习

题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路：一开始发现有很多种情况，最容易想到的是按照中序遍历的遍历顺序来分情况讨论，首先知道中序遍历的顺序是左中右，所以可以大致分为三种情况：

　　1.当前结点处于一趟中序遍历里的“左”状态，则它的下一个结点应该是“中”，即它是左孩子，我们应该从它出发去找它的父亲结点，找到的父亲结点即为下一个结点；
　　2.当前结点处于一趟中序遍历里的“中”状态，则它的下一个结点应该是“右”，即它是中间的结点，要找到边结点的中序遍历里头的第一个节点。即如果右孩子为叶结点，就取该右孩子，如果右孩子结点还有左孩子结点，则找到右孩子结点的最左子节点即是下一个结点。
　　3.当前结点处于一趟中序遍历里的“右状态”，则它的下一个结点应该是下一轮的中序遍历里的左状态。则我们应该要找的是该节点是否含有左子树，如果有左子树就返回该左子树的最左结点，如果没有就返回null，此时已经到了最后一个节点。

　　可以看出来上面三种情况里头有重复的情况，所以再分析一下就发现我们可以简单的分为两种情况来讨论这个问题：即该节点有没有右子树。
　　1.如果该节点有右子树，则它要找的就是该右子树的最左子节点就是下一个结点；
　　2.如果该节点没有右子树，则它要找的就是它的下一个结点是不是它的父节点，且它是这个父节点的左孩子，如果满足这个条件，则下个结点就是要求的结点。

其他情况：输入为空等等均返回null;

java代码如下：

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
 
    	TreeLinkNode node; //定义该辅助结点用来使得pNode的值得以保存
    	
    	//如果该节点有右子树，则找到右子树的最左子节点就是下一个结点
    	
		if(pNode.right!=null) {
			node=pNode.right;
			while(node.left!=null) {
				node=node.left;
			}
			return node;
		}
	
    	//如果该节点没有右子树，则找到满足下一个结点的左孩子是该节点的点，然后取该节点的下一个结点即为要求的下一个结点
    	node=pNode;
    	while(node.next!=null) {
    		if(node.next.left==node) {
    			return node.next;
    		}else {
    			node=node.next;
    		}
    	}
    	return null;
    }
}