第26天--算法（Leetcode 104,105,106,108）
104.二叉树的最大深度
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
if(root.left == null && root.right == null) {
return 1;
}
return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
}
105.从前序与中序遍历构造二叉树
public TreeNode buildTree(int[] preorder, int[] inorder) {
HashMap hm = new HashMap<>();
for(int i = 0;i < inorder.length;i ++) {
hm.put(inorder[i],i);
}
return process(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1,hm);
}
public TreeNode process(int pre[],int L1,int R1,int in[],int L2,int R2,HashMap hm) {
if(L1 > R1) {
return null;
}
TreeNode res = new TreeNode(pre[L1]);
if(L1 == R1) {
return res;
}
int findIndex = hm.get(pre[L1]);
res.left = process(pre,L1 + 1,L1 + findIndex - L2,in,L2,findIndex - 1,hm);
res.right = process(pre,L1 + findIndex - L2 + 1,R1,in,findIndex + 1,R2,hm);
return res;
}
106.从中序与后序遍历序列构造二叉树
public TreeNode buildTree(int[] inorder, int[] postorder) {
HashMap hm = new HashMap<>();
for(int i = 0;i < inorder.length;i ++) {
hm.put(inorder[i],i);
}
return process(inorder,0,inorder.length - 1,postorder,0,postorder.length - 1,hm);
}
public TreeNode process(int[] inorder,int L1,int R1,int[] postorder,int L2,int R2,HashMap hm) {
if(L1 > R1) {
return null;
}
TreeNode res = new TreeNode(postorder[R2]);
if(L1 == R1) {
return res;
}
int findIndex = hm.get(postorder[R2]);
res.left = process(inorder,L1,findIndex - 1,postorder,L2,L2 + findIndex - L1 - 1,hm);
res.right = process(inorder,findIndex + 1,R1,postorder,L2 + findIndex - L1,R2 - 1,hm);
return res;
}
108.将有序数组转换为二叉搜索数
public TreeNode sortedArrayToBST(int[] nums) {
return process(nums,0,nums.length - 1);
}
public TreeNode process(int[] nums,int L,int R) {
if(L > R) {
return null;
}
int mid = (L + R) / 2;
TreeNode res = new TreeNode(nums[mid]);
if(L == R) {
return res;
}
res.left = process(nums,L,mid - 1);
res.right = process(nums,mid + 1,R);
return res;
}