代码随想录【Day20】| 654. 最大二叉树、617. 合并二叉树、700. 二叉搜索树中的搜索、98. 验证二叉搜索树

654. 最大二叉树

题目链接

题目描述：
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。

示例 ：

提示：

给定的数组的大小在 [1, 1000] 之间。
nums 中的所有整数 互不相同

难点：

1. 不能排序，排序会丢失左右位置信息
2. 构造树采用递归前序遍历，如何保留父节点信息，保证构造链不断

思路：

时间复杂度：O()
空间复杂度：O()

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {TreeNode root = constructNode(nums, 0, nums.length);return root;}private TreeNode constructNode(int[] nums, int left, int right) {if (left >= right) {return null;}if (right - left == 1) {return new TreeNode(nums[left]);}int maxValue = 0;int maxIdx = 0;for (int i = left; i < right; i++) {if (nums[i] > maxValue) {maxIdx = i;maxValue = nums[i];}}TreeNode root = new TreeNode(maxValue);root.left = constructNode(nums, left, maxIdx);root.right = constructNode(nums, maxIdx+1, right);return root;}
}

时长：
40min

收获：
构造返回类型为TreeNode的递归函数

---

617. 合并二叉树

题目链接

题目描述：
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

注意: 合并必须从两个树的根节点开始。

难点：

思路：

时间复杂度：O()
空间复杂度：O()

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {root1 = merge(root1, root2);return root1;}//1. 结点1结点2均为空结点//2. 结点1为空，结点2不空 ===> 将结点2赋给结点1//3. 结点1不空，结点2为空 ===> 将结点1返回//4. 结点1结点2均不空    ===> 结点1的值加上结点2的值，递归处理结点1、2左右结点//5. 返回结点1private TreeNode merge(TreeNode root1, TreeNode root2) {if (root1 == null && root2 == null) return null;if (root1 == null && root2 != null) {root1 = root2;}else if (root1 != null && root2 != null) {root1.val += root2.val;root1.left = merge(root1.left, root2.left);root1.right = merge(root1.right, root2.right);}return root1;}
}//简化整理一下
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {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;}
}

时长：
20min

收获：
注意递归返回值

---

700. 二叉搜索树中的搜索

题目链接

题目描述：
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

例如，

在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

难点：

思路：

时间复杂度：O()
空间复杂度：O()

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

时长：
5min

收获：
BST的性质

---

98. 验证二叉搜索树

题目链接

题目描述：
给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。
• 

难点：
不能单纯的比较左节点小于中间节点，右节点大于中间节点

思路：
要记录父节点

时间复杂度：O()
空间复杂度：O()

class Solution {TreeNode maxNode;public boolean isValidBST(TreeNode root) {if (root == null) return true;//左boolean left = isValidBST(root.left);if (!left) {return false;}//中if (maxNode != null && root.val <= maxNode.val) {return false; //中序遍历，maxNode代表当前遍历到的部分的最大值结点，如果遍历右子树，将会更新它}maxNode = root;//右boolean right = isValidBST(root.right);return right;}
}

时长：
12min

收获：
BST的性质，左右节点严格小于大于

本题很巧妙，先从左子树最下面开始判断，逐层返回左子树的根节点和当前树的根节点做判断