根据前序遍历和中序遍历重建二叉树

package com.study;

/*
 * 根据二叉树的前序遍历和中序遍历结果重建二叉树
 * 并输出其头节点。假设前序遍历和中序遍历结果中没有重复数字
 * 前序遍历序列：{1，2，4，7，3，5，6，8}
 * 中序遍历序列：{4，7，2，1，5，3，8，6}
 * **/
class TreeNode {
	public int data;
	public TreeNode left;
	public TreeNode right;
	
	public TreeNode() {
		
	}
}


public class suanfa4 {
	
	private static int[] arr1 = {1,2,4,7,3,5,6,8};
	private static int[] arr2 = {4,7,2,1,5,3,8,6};
	public static TreeNode RebuildBinaryTree() {
		TreeNode head = null;
		head = ConstructBTree( head ,arr1, 0, 7, arr2, 0, 7);
		return head;
	}
	
	public static TreeNode ConstructBTree(TreeNode node, int[] pre, int pre_start, int pre_end,
			int[] inorder, int inorder_start, int inorder_end) {
		//System.out.println("pre_start:" + pre_start);
		//System.out.println("pre_end: "+ pre_end);
		/*if(pre_start > pre_end || pre_end > pre.length) 
			return null;*/ 
		/*刚开始想着这里应该增加这样一个递归结束条件，但是在调试的过程中发现，如果增加了的话，则不能将最后
			的叶子节点加到二叉树中，而且后面的判断左子树长度和右子树长度会自然结束递归*/
		TreeNode root = new TreeNode();
		root.data = pre[pre_start]; //找到根节点
		root.left = root.right = null;

		//System.out.println("root :"+ root.data);
		int pos = FindPos(root.data, inorder); //在中序遍历的数组中找到根节点的位置
		int Left_Length = pos - inorder_start;
		int Right_Length = inorder_end - pos;
		//System.out.println("左子树长度" + Left_Length);
		//System.out.println("右子树长度" + Right_Length);
		
		if( Left_Length > 0) {   //存在左子树
			TreeNode LeftRoot = new TreeNode();
			LeftRoot.data = pre[pre_start + 1]; //左根节点
			root.left = ConstructBTree(LeftRoot, pre , pre_start + 1, pre_start + Left_Length, inorder,
					inorder_start , pos - 1);			
		}
		
		if( Right_Length > 0) { //存在右子树
			TreeNode RightRoot = new TreeNode();
			RightRoot.data = pre[pre_start + Left_Length + 1]; //右根节点
			root.right = ConstructBTree(RightRoot, pre , pre_start + Left_Length + 1 , pre_start + Left_Length
					+ Right_Length - 1, inorder, pos + 1 , inorder_end);
		}
		
		return root;		
	}
	
	public static int FindPos(int num, int arr[]) {
		int i = 0;
		if(arr != null) {
			while(arr[i] != num)
				i++;
			if(arr[i] == num)
				return i;
		}
		
		return -1;		
	}
	
	/*后序遍历*/
	public static void LastOrder(TreeNode head) {
		if( head != null) {
			LastOrder(head.left);
			LastOrder(head.right);
			System.out.println(head.data);
		}
	}
	
	
	public static void main(String[] args) {
		TreeNode tnode = RebuildBinaryTree();
		LastOrder(tnode);
	}
}

费了好半天劲才弄出来，有两点感想：

1.如上图代码中被注释掉的打印语句一样，有时调试程序中的逻辑错误，尤其是令人头大的递归，添加打印语句比单步调试更为简单直白，不然，单步跟踪，调着调着就被绕进去了（智商不高，见谅！）

2.虽然这次是参考着剑指offer上的答案弄出来的，但是还是颇有感触。一定要敢想，坚信一个道理：一切反动派都是纸老虎。尤其是递归，要注意函数的参数。有时候最简单的思路，往往容易被忽视。继续努力！

---

今天晚上，在牛客网上做剑指offer的题的时候，发现其实自己之前写的代码还可以继续精简一点，看着思路更清晰。

	package com.study;
	
	/*
	 * 根据二叉树的前序遍历和中序遍历结果重建二叉树
	 * 并输出其头节点。假设前序遍历和中序遍历结果中没有重复数字
	 * 前序遍历序列：{1，2，4，7，3，5，6，8}
	 * 中序遍历序列：{4，7，2，1，5，3，8，6}
	 * **/
	class TreeNode {
		public int data;
		public TreeNode left;
		public TreeNode right;
		
		public TreeNode() {
			
		}
	}


	public class suanfa4 {
		
		private static int[] arr1 = {1,2,4,7,3,5,6,8};
		private static int[] arr2 = {4,7,2,1,5,3,8,6};
		public static TreeNode RebuildBinaryTree() {
			TreeNode head = null;
			//head = ConstructBTree( head ,arr1, 0, 7, arr2, 0, 7);
			head = ConstructBTree(arr1, 0, 7, arr2, 0, 7);
			return head;
		}
		
		public static TreeNode ConstructBTree(int[] pre, int pre_start, int pre_end,
				int[] inorder, int inorder_start, int inorder_end) {
			if(pre_start > pre_end || pre_end > pre.length) 
				return null; 
			TreeNode root = new TreeNode();
			root.data = pre[pre_start]; //找到根节点
			root.left = root.right = null;
	
			int pos = FindPos(root.data, inorder); //在中序遍历的数组中找到根节点的位置
			int Left_Length = pos - inorder_start;
			int Right_Length = inorder_end - pos;
			
			if( Left_Length > 0) {   //存在左子树
				root.left = ConstructBTree (pre , pre_start + 1, pre_start + Left_Length, inorder,
						inorder_start , pos - 1);			
			}
			
			if( Right_Length > 0) { //存在右子树
				root.right = ConstructBTree(pre , pre_start + Left_Length + 1 , pre_start + Left_Length
						+ Right_Length, inorder, pos + 1 , inorder_end);
			}
			
			return root;		
		}
		
		
		
		
		public static int FindPos(int num, int arr[]) {
			int i = 0;
			if(arr != null) {
				while(arr[i] != num)
					i++;
				if(arr[i] == num)
					return i;
			}
			
			return -1;		
		}
		
		/*后序遍历*/
		public static void LastOrder(TreeNode head) {
			if( head != null) {
				LastOrder(head.left);
				LastOrder(head.right);
				System.out.println(head.data);
			}
		}
		
		
		public static void main(String[] args) {
			TreeNode tnode = RebuildBinaryTree();
			LastOrder(tnode);
		}
	}