二叉树的构造（前后序用来确定根的位置，中用来划分左右子树

最大二叉树（递归要先写终止条件 终止条件 终止条件

每次找最大的结点为分界点以及根节点，左边构成左子树，右边构成右子树，递归

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return build(nums,0,nums.length-1);}TreeNode build(int[] nums,int left,int right){if(left>right) return null;int index=-1,maxVal=Integer.MIN_VALUE;for(int i=left;i<=right;i++){if(nums[i]>maxVal){maxVal=nums[i];index=i;}}TreeNode root=new TreeNode(maxVal);root.left=build(nums,left,index-1);root.right=build(nums,index+1,right);return root;}
}

通过前序和中序遍历结果构造二叉树

关键点在于找到左子树的数量 ，可以用hashmap保存inorder的映射，提高效率

主要就是pre 和in 的start和end，以及leftsize

写代码时不能用具体数值，要用形参，因为是递归，所以 用形参来放入即可

        

class Solution {Map<Integer,Integer> map=new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);//创建映射方便查找索引}return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}TreeNode build(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){if(preStart>preEnd) return null;int val=preorder[preStart];//这里不能用0！TreeNode root=new TreeNode(val);int index=map.get(val);int leftSize=index-inStart;root.left=build(preorder,preStart+1,preStart+leftSize,inorder,inStart,index-1);root.right=build(preorder,preStart+leftSize+1,preEnd,inorder,index+1,inEnd);return root;}
}

用根节点来当分界点，所以index为根节点

class Solution {Map<Integer,Integer> map=new HashMap<>();public TreeNode buildTree(int[] inorder, int[] postorder) {for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);//创建中序遍历的映射}return build(inorder,0,inorder.length-1,postorder,0,postorder.length-1);}public TreeNode build(int[] inorder,int inStart,int inEnd,int[] postorder,int poStart,int poEnd){if(inStart>inEnd) return null;int val=postorder[poEnd];TreeNode root=new TreeNode(val);int index=map.get(val);int leftSize=index-inStart;root.left=build(inorder,inStart,index-1,postorder,poStart,leftSize+poStart-1);root.right=build(inorder,index+1,inEnd,postorder,poStart+leftSize,poEnd-1);return root;}
}

class Solution {Map<Integer,Integer> map=new HashMap<>();public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {for(int i=0;i<postorder.length;i++){map.put(postorder[i],i);//后序遍历的映射}return build(preorder,0,preorder.length-1,postorder,0,postorder.length-1);}public TreeNode build(int[] preorder,int preStart,int preEnd,int[] postorder,int poStart,int poEnd){if (preStart > preEnd) {return null;}if (preStart == preEnd) {return new TreeNode(preorder[preStart]);//防止数组越界！}int val=preorder[preStart];TreeNode root=new TreeNode(val);int leftVal=preorder[preStart+1];int index=map.get(leftVal);int leftSize=index-poStart+1;root.left=build(preorder,preStart+1,preStart+leftSize,postorder,poStart,index);root.right=build(preorder,preStart+leftSize+1,preEnd,postorder,index+1,poEnd-1);return root;}
}