Day17--654.最大二叉树+617.合并二叉树+700.二叉搜索树中的搜索+ 98.验证二叉搜索树

一、654.最大二叉树

题目链接：https://leetcode.cn/problems/maximum-binary-tree/
文章讲解：https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV1MG411G7ox

1.1 初见思路

找到数组中的最大数，构建中节点，最大数的左边为左子树的数据，右边是右子树的数据

2. 递归

1.2 具体实现

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return constructMaximumBinaryTree1(nums, 0, nums.length);}public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {if (rightIndex - leftIndex == 0) {return null;}int maxValue = Integer.MIN_VALUE;int maxIndex = -1;for (int i = leftIndex; i < rightIndex; i++) {if (nums[i] > maxValue) {maxIndex = i;maxValue = nums[i];}}TreeNode node = new TreeNode(maxValue);node.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);node.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);return node;}
}

1.3 重难点

二、 617.合并二叉树

题目链接：https://leetcode.cn/problems/merge-two-binary-trees/
文章讲解：https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV1m14y1Y7JK

2.1 初见思路

同时遍历两个树

2.2 具体实现

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {TreeNode root = new TreeNode();if(root1==null){root=root2;}if(root2==null){root = root1;}if(root1!=null && root2!=null){root.val=root1.val+root2.val;root.left=mergeTrees(root1.left,root2.left);root.right=mergeTrees(root1.right,root2.right);}return root;}
}

2.3 重难点

三、 700.二叉搜索树中的搜索

题目链接：https://leetcode.cn/problems/search-in-a-binary-search-tree/
文章讲解：https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html
视频讲解：https://www.bilibili.com/video/BV1wG411g7sF

3.1 初见思路

熟悉二叉搜索树的定义，左子树的所有节点的值都小于中节点，右子树的所有节点的值都大于中节点

3.2 具体实现

class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root==null){return null;}if(root.val>val){return searchBST(root.left,val);}if(root.val<val){return searchBST(root.right,val);}return root;}
}

3.3 重难点

四、 98.验证二叉搜索树

题目链接：https://leetcode.cn/problems/validate-binary-search-tree/
文章讲解：https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV18P411n7Q4

4.1 初见思路

4.2 具体实现

class Solution {// 递归TreeNode max;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}// 左boolean left = isValidBST(root.left);if (!left) {return false;}// 中：一直更新maxVal，一旦发现maxVal >= root->val，就返回false，注意元素相同时候也要返回false。if (max != null && root.val <= max.val) {return false;}max = root;// 右boolean right = isValidBST(root.right);return right;}
}