前言
书接上篇文章二叉树习题其二,这篇文章我们将基础拓展
###我做这类文档一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非常非常高滴!!!
习题
1.从中序与后序遍历序列构造二叉树
题目链接:106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode)
题面:
基本分析:后序遍历数组的最后一个值其实就是根节点,由于中序遍历的顺序是前中后,那么我们在中序数组中定位到根节点的位置,例如上图样例是3,那么在 3左边的就是左子树,右边的就是右子树,这就是递归的一个过程,然后使用递归
/**
* 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<>();
int[] postorderflag;
public TreeNode buildTree(int[] inorder, int[] postorder) {
int n = inorder.length-1;
for(int i = 0;i<=n;i++)map.put(inorder[i],i);
postorderflag = postorder;
return recursion(0,n,0,n);
}
public TreeNode recursion(int is,int ie,int ps,int pe){
if(is>ie||ps>pe)return null;
int root = postorderflag[pe];
TreeNode node = new TreeNode(root);
int ri = map.get(root);
node.left = recursion(is,ri-1,ps,ps+ri-is-1);
node.right = recursion(ri+1,ie,ps+ri-is,pe-1);
return node;
}
}
2.最大二叉树
题目链接:654. 最大二叉树 - 力扣(LeetCode)
题面:
基本分析:就是区间找最值然后构造树
代码:
/**
* 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 {
int numsflag[];
Map<Integer,Integer> map = new HashMap<>();
public TreeNode constructMaximumBinaryTree(int[] nums) {
numsflag = nums;
int n = nums.length-1;
for(int i = 0;i<=n;i++)map.put(nums[i],i);
return recursion(0,n);
}
public TreeNode recursion(int l,int r){
if(l>r)return null;
int max = Integer.MIN_VALUE;
for(int i = l;i<=r;i++){
if(numsflag[i]>max)max = numsflag[i];
}
int index = map.get(max);
TreeNode node = new TreeNode(max);
node.left = recursion(l,index -1);
node.right = recursion(index+1,r);
return node;
}
}
3.合并二叉树
题目链接:617. 合并二叉树 - 力扣(LeetCode)
题面:
基本分析:两者同时遍历
/**
* 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 mergeTrees(TreeNode root1, TreeNode root2) {
return recursion(root1,root2);
}
public TreeNode recursion(TreeNode root1, TreeNode root2){
TreeNode node = new TreeNode(Integer.MAX_VALUE);
if(root1==null&&root2==null)return null;
if(root1==null||root2==null){
return root1==null?root2:root1;
}
node.val=(root2.val+root1.val);
node.left = recursion(root1.left,root2.left);
node.right = recursion(root1.right,root2.right);
return node;
}
}
4.二叉搜索树中的搜索
题目链接:700. 二叉搜索树中的搜索 - 力扣(LeetCode)
题面:
基本分析:就是遍历
代码:
/**
* 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 {
TreeNode ans = new TreeNode(Integer.MAX_VALUE);
int flag = 0;
public TreeNode searchBST(TreeNode root, int val) {
flag = val;
recursion(root);
return ans.val==Integer.MAX_VALUE?null:ans;
}
public void recursion(TreeNode node){
if(node==null)return;
if(node.val==flag)ans = node;
recursion(node.left);
recursion(node.right);
}
}
5.验证二叉搜索树
题目链接:98. 验证二叉搜索树 - 力扣(LeetCode)
题面:
基本分析:采用限定范围的思想可以规避很多变量的维护
代码:
/**
* 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 {
ArrayList<Integer> listleft = new ArrayList<>();
ArrayList<Integer> listright = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
return recursion(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
public boolean recursion(TreeNode node,long left,long right){
if(node==null)return true;
long flag = node.val;
return flag>left&&flag<right&&recursion(node.left,left,flag)&&recursion(node.right,flag,right);
}
}
后言
上面是二叉树的部分习题,下一篇会讲解二叉树的其他相关力扣习题,希望有所帮助,一同进步,共勉!
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » 二叉树习题其三-Java【力扣】【算法学习day.10】
发表评论 取消回复