105. 从前序与中序遍历序列构造二叉树 + 106后序和中序构造

105. 从前序与中序遍历序列构造二叉树

难度：中等 2020/5/22每日一题打卡√

题目描述

解题思路

这种题目也是考研的时候经常写，但是是用手算，知道方法，但是用代码写起来有点模糊

/*
	   * 105. 从前序与中序遍历序列构造二叉树
	   * 2020/5/22每日一题打卡
	   */
	  public TreeNode buildTree(int[] preorder, int[] inorder) {
		  HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
		  for (int i = 0; i < inorder.length; i++) {  //用哈希表保存中序遍历中每个节点的位置信息
			hashMap.put(inorder[i], i);
		}
		  return bulidHelper(preorder,inorder,0,preorder.length-1,0,hashMap);
	    }
	  public TreeNode bulidHelper(int[] preorder,int[] inorder,int begin,int end,int mid,HashMap<Integer, Integer> hashMap) {
		  if(begin > end) {
			  return null;
		  }
		  //创建根节点
		  int rootval = preorder[mid];
		  System.out.println(begin+" "+end+" "+mid);
		  TreeNode root = new TreeNode(preorder[mid]);
		  //找到前序遍历中的根节点在中序遍历中的位置
		  int i = hashMap.get(rootval);
		  root.left = bulidHelper(preorder, inorder, begin, i-1,mid+1,hashMap);  //递归生成左子树
		  root.right = bulidHelper(preorder, inorder, i+1, end,mid+i-begin+1,hashMap);  //递归生成右子树
		  return root;
	}
           

1. 从中序与后序遍历序列构造二叉树

   就完全是一样的，救之哟啊改一下下标就可以了，后序遍历左右根，所以最后一个元素是根

public TreeNode buildTree(int[] inorder, int[] postorder) {
		  HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
		  for (int i = 0; i < inorder.length; i++) {  //用哈希表保存中序遍历中每个节点的位置信息
			hashMap.put(inorder[i], i);
		}
		  return bulidHelper(postorder,inorder,0,postorder.length-1,postorder.length-1,hashMap);
	    }
	  public TreeNode bulidHelper(int[] preorder,int[] postorder,int begin,int end,int mid,HashMap<Integer, Integer> hashMap) {
		  if(begin > end) {
			  return null;
		  }
		  //创建根节点
		  int rootval = preorder[mid];
		  TreeNode root = new TreeNode(preorder[mid]);
		  //找到前序遍历中的根节点在中序遍历中的位置
		  int i = hashMap.get(rootval);
		  root.left = bulidHelper(preorder, postorder, begin, i-1,mid-end+i-1,hashMap);  //递归生成左子树
		  root.right = bulidHelper(preorder, postorder, i+1, end,mid-1,hashMap);  //递归生成右子树
		  return root;
	}