力扣爆刷第142天之二叉树五连刷（构造树、搜索树）

力扣爆刷第142天之二叉树五连刷（构造树、搜索树）

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

题目链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
思路：首先把中序遍历的key和value用map记录下来，节省通过后序定位根节点的时间，然后不断的用父节点划分左右子数组。

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 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, leftPo+mid-leftIn-1);root.right = traverse(inorder, postorder, mid+1, rightIn, leftPo+mid-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, mid+1, 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);}
}