代码随想录三刷day21

本文主要是介绍代码随想录三刷day21，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
一、力扣113. 路径总和 II
二、力扣106. 从中序与后序遍历序列构造二叉树
三、力扣105. 从前序与中序遍历序列构造二叉树
四、力扣654. 最大二叉树

前言

构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。

一、力扣113. 路径总和 II

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {if(root == null){return res;}fun(root,targetSum-root.val);return res;}public void fun(TreeNode root, int targetSum){path.add(root.val);if(root.left == null && root.right == null){if(targetSum == 0){res.add(new ArrayList<>(path));}return;}if(root.left != null){fun(root.left,targetSum-root.left.val);path.remove(path.size()-1);}if(root.right != null){fun(root.right , targetSum-root.right.val);path.remove(path.size()-1);}}
}

二、力扣106. 从中序与后序遍历序列构造二叉树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
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);}int len = inorder.length;return fun(inorder, postorder, 0, len-1, 0,len -1,len);}public TreeNode fun(int[] inorder, int[] postorder,int ins,int ine,int posts,int poste,int len){if(posts > poste){return null;}int v = postorder[poste];TreeNode root = new TreeNode(v);int index = map.get(v);root.left = fun(inorder, postorder, ins, index-1, posts,posts+index-ins-1,len);root.right = fun(inorder,postorder,index+1,ine,posts+index-ins,poste-1,len);return root;}
}

三、力扣105. 从前序与中序遍历序列构造二叉树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {Map<Integer,Integer> map = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length-1;for(int i = 0; i <= n; i ++){map.put(inorder[i],i);}return fun(preorder, inorder, 0, n, 0,n);}public TreeNode fun(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd){if(preStart > preEnd){return null;}int index = map.get(preorder[preStart]);TreeNode root = new TreeNode(preorder[preStart]);root.left = fun(preorder, inorder, preStart+1,preStart+index-inStart,inStart, index-1);root.right = fun(preorder, inorder, preStart+index-inStart+1,preEnd,index+1,inEnd );return root;}
}

四、力扣654. 最大二叉树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return fun(nums,0,nums.length-1);}public TreeNode fun(int[] nums, int start, int end){if(start > end){return null;}int index = f(nums,start,end);TreeNode root = new TreeNode(nums[index]);root.left = fun(nums,start,index-1);root.right = fun(nums,index+1,end);return root;}public int f(int[] nums, int start, int end){int max = Integer.MIN_VALUE;int index = start;for(int i = start; i <= end; i ++){if(nums[i] >= max){max = nums[i];index = i;}}return index;}
}