面试题8：二叉树的下一个节点

题目：给定一个二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。

思路：以图一为例分析，图一二叉树的中序序列为{d,b,h,e,i,a,f,c,g}，分几种情况：

1）一个节点有右子树，那么该节点的下一个节点就是右子树的最左子节点

2）一个节点没有右子树，如果该节点是其父节点的左子节点，那么它的下一个节点就是它的父节点；否则它的下一个节点就是它的祖先节点中某个节点且该祖先节点是其父节点的左子节点

解法：

package question8;

public class NextNode {
	class TreeNode{
		String value;
		TreeNode parent;
		TreeNode left;
		TreeNode right;
		public TreeNode(String value,TreeNode parent,TreeNode left,TreeNode right) {
			this.value=value;
			this.parent=parent;
			this.left=left;
			this.right=right;
		}
	}
	public static void main(String[] args) {
		NextNode node=new NextNode();
		TreeNode g = node.new TreeNode("g", null , null, null);
		TreeNode f = node.new TreeNode("f", null , null, null);
		TreeNode c = node.new TreeNode("c", null , f, g);
		TreeNode h = node.new TreeNode("h", null , null, null);
		TreeNode i = node.new TreeNode("i", null , null, null);
		TreeNode e = node.new TreeNode("e", null , h, i);
		TreeNode d = node.new TreeNode("d", null , null, null);
		TreeNode b = node.new TreeNode("b", null , d, e);
		TreeNode a = node.new TreeNode("a", null , b, c);
		b.parent=c.parent=a;
		d.parent=e.parent=b;
		h.parent=i.parent=e;
		f.parent=g.parent=c;
		TreeNode node1 = findNextNode(f);
		if(node1!=null){
			System.out.println("下一个节点是"+node1.value);
		}else{
			System.out.println("下一个节点是null");
		}
	}
	private static TreeNode findNextNode(TreeNode treeNode) {
		if(treeNode==null){
			return null;
		}
		if(treeNode.right!=null){
			TreeNode rightNode=treeNode.right;
			while(rightNode.left!=null){
				rightNode=rightNode.left;
			}
			return rightNode;
		}else if(treeNode.parent!=null){
			TreeNode currentNode=treeNode;
			TreeNode parentNode=treeNode.parent;
			while(parentNode!=null&&currentNode==parentNode.right){
				currentNode=parentNode;
				parentNode=parentNode.parent;
			}
			return parentNode;
		}
		
		return null;
		
	}
}