长沙征帆网站建设,做网站还要做点手机吗,不用模板 网站,互联网十大上市公司力扣爆刷第142天之二叉树五连刷#xff08;构造树、搜索树#xff09; 文章目录 力扣爆刷第142天之二叉树五连刷#xff08;构造树、搜索树#xff09;一、106. 从中序与后序遍历序列构造二叉树二、654. 最大二叉树三、617. 合并二叉树四、700. 二叉搜索树中的搜索五、98. …力扣爆刷第142天之二叉树五连刷构造树、搜索树 文章目录 力扣爆刷第142天之二叉树五连刷构造树、搜索树一、106. 从中序与后序遍历序列构造二叉树二、654. 最大二叉树三、617. 合并二叉树四、700. 二叉搜索树中的搜索五、98. 验证二叉搜索树 一、106. 从中序与后序遍历序列构造二叉树
题目链接https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/ 思路首先把中序遍历的key和value用map记录下来节省通过后序定位根节点的时间然后不断的用父节点划分左右子数组。
class Solution {MapInteger, 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 traverse(inorder, postorder, 0, inorder.length-1, 0, postorder.length-1);}TreeNode traverse(int[] inorder, int[] postorder, int leftIn, int rightIn, int leftPo, int rightPo) {if(leftIn rightIn) return null;int mid map.get(postorder[rightPo]);TreeNode root new TreeNode(postorder[rightPo]);root.left traverse(inorder, postorder, leftIn, mid-1, leftPo, leftPomid-leftIn-1);root.right traverse(inorder, postorder, mid1, rightIn, leftPomid-leftIn, rightPo-1);return root;}}二、654. 最大二叉树
题目链接https://leetcode.cn/problems/maximum-binary-tree/description/ 思路也是前序遍历构建二叉树在每一次指定区间的内通过比较获取最大值然后通过最大值划分左右子数组。
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return buildTree(nums, 0, nums.length-1);}TreeNode buildTree(int[] nums, int left, int right) {if(left right) return null;int max nums[left], mid left;for(int i left; i right; i) {if(nums[i] max) {max nums[i];mid i;}}TreeNode root new TreeNode(max);root.left buildTree(nums, left, mid-1);root.right buildTree(nums, mid1, right);return root;}
}三、617. 合并二叉树
题目链接https://leetcode.cn/problems/merge-two-binary-trees/description/ 思路合并二叉树其实就是遍历其中一棵树然后把另外一颗树连接到这棵树上。
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1 null root2 null) {return null;}if(root1 null) return root2;if(root2 null) return root1;root1.val root2.val;root1.left mergeTrees(root1.left, root2.left);root1.right mergeTrees(root1.right, root2.right);return root1;}}四、700. 二叉搜索树中的搜索
题目链接https://leetcode.cn/problems/search-in-a-binary-search-tree/description/ 思路利用二叉搜索树的特性从上往下进行搜索相等返回小于去左子树大于去右子树。
class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root null) return null;if(root.val val) {return root;}else if(root.val val) {return searchBST(root.left, val);}else{return searchBST(root.right, val);}}}五、98. 验证二叉搜索树
题目链接https://leetcode.cn/problems/validate-binary-search-tree/description/ 思路要想验证是不是二叉搜索树直接利用二叉搜索树的特性中序单调遍历递增只要非单调递增即不是。
class Solution {boolean flag true;TreeNode p null;public boolean isValidBST(TreeNode root) {traverse(root);return flag;}void traverse(TreeNode root) {if(root null) return ;traverse(root.left);if(p ! null) {if(p.val root.val) {flag false;return ;}}p root;traverse(root.right);}
}
