在leetcode上有两题，分别是根据前序/后序 和中序遍历重构二叉树。思路都是一样的，但是要记住，在从后序遍历重构二叉树的时候，要先从右子树进行建立，因为后序遍历先遍历的是右子树。
前序遍历+中序遍历
（1）首先进行边界判断，如果遍历数组为0或者1的情况下，说明这个树只有一个顶点或者没有顶点，直接进行构造。 （2）根据前序遍历和中序遍历建立二叉树的思路是：前序遍历依次每一个节点对应一个子树，这个节点在中序遍历中找到它相应的位置，它的左边（当然是在子树数组范围内）就是左子树的顶点，右边就是右子树的顶点。
前序遍历就是确定树的根节点，中序遍历就是确定树的左右子树。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int preIndex = 0; int[] preorder; int[] inorder; Map<Integer, Integer> map = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder.length == 0) return null; if(preorder.length == 1) return new TreeNode(preorder[0]); this.preorder = preorder; this.inorder = inorder; int len = inorder.length; for(int i = 0; i < len; i++){ map.put(inorder[i], i); } TreeNode res = func(0, len-1); return res; } public TreeNode func(int l, int r){ if(l > r) return null; TreeNode root = new TreeNode(preorder[preIndex]); int inIndex = map.get(preorder[preIndex]); preIndex++; root.left = func(l, inIndex-1); root.right = func(inIndex+1, r); return root; } }后序遍历+中序遍历
代码相同，注意的是需要先构建右子树。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { Map<Integer, Integer> map; int postIndex; public TreeNode buildTree(int[] inorder, int[] postorder) { int len = inorder.length; if(len == 0) return null; if(len == 1) return new TreeNode(inorder[0]); map = new HashMap<>(); postIndex = len-1; for(int i = 0; i < len; i++) { map.put(inorder[i], i); } TreeNode res = fuc(0, len-1, inorder, postorder); return res; } public TreeNode fuc(int l, int r, int[] inorder, int[] postorder){ if(l > r) return null; TreeNode newNode = new TreeNode(postorder[postIndex]); System.out.println(newNode.val); int inIndex = map.get(postorder[postIndex]); postIndex--; newNode.right = fuc(inIndex+1, r, inorder, postorder); newNode.left = fuc(l, inIndex-1, inorder, postorder); return newNode; } }