代码随想录-刷题第二十天

654.最大二叉树

题目链接：654. 最大二叉树

思路：确定根节点，并且不断构造左右子树。函数 build 的定义是根据输入的数组构造最大二叉树，那么只要先要找到根节点，然后让 build 函数递归生成左右子树即可。

class Solution {/* 主函数 */public TreeNode constructMaximumBinaryTree(int[] nums) {return build(nums, 0, nums.length - 1);}/* 定义：将 nums[lo..hi] 构造成符合条件的树，返回根节点 */TreeNode build(int[] nums, int lo, int hi) {// base caseif (lo > hi) {return null;}// 找到数组中的最大值和对应的索引int index = -1, maxVal = Integer.MIN_VALUE;for (int i = lo; i <= hi; i++) {// i 可以取到 hiif (maxVal < nums[i]) {index = i;maxVal = nums[i];}}TreeNode root = new TreeNode(maxVal);// 递归调用构造左右子树root.left = build(nums, lo, index - 1);root.right = build(nums, index + 1, hi);return root;}}

617.合并二叉树

题目链接：617. 合并二叉树

思路：前序递归遍历，根据题目条件构造节点，迭代法（层序遍历）同样可以完成。

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

700.二叉搜索树中的搜索

题目链接：700. 二叉搜索树中的搜索

思路：递归法和迭代法，利用BST 左小右大的特性，可以避免搜索整棵二叉树去寻找元素，从而提升效率。

递归法：

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;}}

迭代法：

class Solution {// 迭代法public TreeNode searchBST(TreeNode root, int val) {while (root != null) {if (root.val == val) return root;if (root.val > val) {root = root.left;} else {root = root.right;}}return root;}}

98.验证二叉搜索树

题目链接：98. 验证二叉搜索树

思路：首先要知道，二叉搜索树的中序遍历是一个有序序列。可以对二叉搜索树进行中序遍历，将结果放入数组中，只需要判断数组是否有序即可。

class Solution {private List<Integer> list = new ArrayList<>();// 二叉搜索树中序遍历下，输出的节点数值是有序序列。public boolean isValidBST(TreeNode root) {inorder(root);for (int i = 1; i < list.size(); i++) {// 注意要大于等于，搜索树里不能有相同元素if (list.get(i - 1) >= list.get(i)) {return false;}}return true;}public void inorder(TreeNode node) {if (node == null) return;inorder(node.left);list.add(node.val);inorder(node.right);return;}}

递归解法：因为BST左小右大的特性是指 root.val 要比左子树的所有节点都更大，要比右子树的所有节点都小，只检查左右两个子节点显然是不够的。

class Solution {public boolean isValidBST(TreeNode root) {// 我们通过使⽤辅助函数，增加函数参数列表，在参数中携带额外信息，// 将这种约束传递给⼦树的所有节点，这也是⼆叉树算法的⼀个⼩技巧吧。return isValidBST(root, null, null);}/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {// base caseif (root == null) return true;// 若 root.val 不符合 max 和 min 的限制，说明不是合法 BSTif (min != null && root.val <= min.val) return false;if (max != null && root.val >= max.val) return false;// 限定左子树的最大值是 root.val，右子树的最小值是 root.valreturn isValidBST(root.left, min, root)&& isValidBST(root.right, root, max);}}