从前序、中序、后序序列构造二叉树
👀💬根据一棵树的中序遍历与后序遍历构造二叉树（LeetCode-106）。
🙅注意:你可以假设树中没有重复的元素。
👊例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
🙋递归解法：
💁思路：
右序序列的右边界值一定为root节点，左边界值一定为最左节点。
用一个常量postInx表示后序序列的下标，初始化值为postorder.length-1每递归一次减1。
用一个Map来存放中序序列：key=node_val，value=index。
采用递归hepler(int left_index,int right_index),两个参数分别为中序序列中当前子树的左右边界值。
int postInx;int[] postOrderArray;HashMap<Integer, Integer> map =new HashMap<>();public TreeNode buildTree(int[] inOrderArray, int[] postOrderArray) {this.postInx = postOrderArray.length -1;this.postOrderArray = postOrderArray;for (int i = 0; i < inOrderArray.length; i++) {map.put(inOrderArray[i], i);}return helper(0, inOrderArray.length - 1);}private TreeNode helper(int in_left, int in_right) {if (in_left > in_right) {return null;}int node_val = postOrderArray[postInx];TreeNode root = new TreeNode(node_val);int inx = map.get(node_val);postInx--;root.right = helper(inx + 1, in_right);root.left = helper(in_left, inx - 1);return root;}
👀💬根据一棵树的前序遍历与中序遍历构造二叉树（LeetCode-105）。
🙅注意:你可以假设树中没有重复的元素。
👊例如，给出
中序遍历 inorder = [4,2,1,5,3,6]
后序遍历 postorder = [,12,4,3,5,6]
返回如下的二叉树：
1
/ \
2 3
/ / \
4 5 6
🙋递归解法：
💁思路：
和LeetCode-106思路差不多，前序序列的第一个元素一定是树的根节点，用一个常量preInx来表示前序遍历的序列下标，每递归一次加1。
用一个Map来存放中序序列的数据，key=序列值，value=下标。
递归函数helper(int in_left, int in_right), 两个参数分别代表中序序列的左右边界值。
int preInx=0;int[] preorder;HashMap<Integer,Integer> map = new HashMap();public TreeNode buildTree(int[] preorder, int[] inorder) {this.preorder = preorder;for(int i =0;i<inorder.length;i++){map.put(inorder[i],i);}return helper(0 , preorder.length-1);}private TreeNode helper(int in_left,int in_right){if(in_left > in_right){return null;}int root_val = preorder[preInx];TreeNode root = new TreeNode(root_val);int index = map.get(root_val);preInx++;root.left = helper(in_left,index -1);root.right = helper(index +1 ,in_right);return root;}
不积跬步，无以至千里。
文章有帮助的话，在看，转发吧。
谢谢支持哟 (*^__^*)
END
👇