DAY20|654.最大二叉树，617.合并二叉树，700.二叉搜索树中的搜索，98.验证二叉搜索树

本文主要是介绍DAY20|654.最大二叉树，617.合并二叉树，700.二叉搜索树中的搜索，98.验证二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 654.最大二叉树
- 617.合并二叉树
- 700.二叉搜索树中的搜索
- 98.验证二叉搜索树（重要）

654.最大二叉树

文字讲解：最大二叉树

视频讲解：最大二叉树

状态：ok

思路：

1、这题和昨天的，通过中序和后序遍历构建二叉树类似，此题相当于通过前序来构建二叉树；但是通过中序和后序来构建二叉树，需要借助两个数组来完成，而此题则需要仅需一个数据可完成；

2、先取数组中的最大值，获取其下标，按照该下标将数组分为左右两个数组，分别为左子树和右子树的元素。

3、然后分别按照步骤2进行递归构建该二叉树并且返回；

class Solution {Map<Integer, Integer> valMap = new HashMap<>();public TreeNode constructMaximumBinaryTree(int[] nums) {for (int i = 0; i < nums.length; i++) {valMap.put(nums[i], i);}return buildMaxTree(nums, 0, nums.length-1);}public TreeNode buildMaxTree(int[] nums, int startIndex, int endIndex) {if (startIndex > endIndex) {return null;}Integer maxNodeVal = getMaxNodeVal(nums, startIndex, endIndex);Integer index = valMap.get(maxNodeVal);TreeNode root = new TreeNode(maxNodeVal);root.left = buildMaxTree(nums, startIndex, index-1);root.right = buildMaxTree(nums, index+1, endIndex);return root;}public Integer getMaxNodeVal(int[] nums, int startIndex, int endIndex) {int max = Integer.MIN_VALUE;for (int i = startIndex; i <= endIndex; i++) {if (nums[i] > max) {max = nums[i];}}return max;}
}

617.合并二叉树

文字讲解：合并二叉树

视频讲解：代码随想录-合并二叉树

状态：看到这道题有点懵逼，不知道如何下手

思路：

1、强调一下 – T^T — ，递归三部曲，确定好入参,确定好退出条件，确认单层递归逻辑；二刷时不明白再看视频继续加深印象；

代码：

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {return rightMergeLeftTree(root1, root2);}public TreeNode rightMergeLeftTree(TreeNode leftNode, TreeNode rightNode) {if (leftNode == null) return rightNode;if (rightNode == null) return leftNode;//当两个node都不为空的时候leftNode.val = leftNode.val + rightNode.val;leftNode.left = rightMergeLeftTree(leftNode.left, rightNode.left);leftNode.right = rightMergeLeftTree(leftNode.right, rightNode.right);return leftNode;}
}

700.二叉搜索树中的搜索

文字讲解：二叉搜索树中的搜索

视频讲解：代码随想录-二叉搜索树中的搜索

状态：这题so easy了

思路：

1、递归三部曲，入参已确定，判断退出条件为节点为空的时候，递归逻辑为，先判断当前节点的val是否等于搜索值，等于则返回，不等则判断当前node的val比是否比搜索值大，如果大则搜索right子节点，否则搜索left左节点；

代码：

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);} else {return searchBST(root.right, val);}}
}

98.验证二叉搜索树（重要）

文字讲解：验证二叉搜索树

视频讲解：代码随想录-验证二叉搜索树

状态：

思路：

1、这题真是给坑就踩进去了，BSF不是简单的理解为每个节点的左子树的值比父节点小，每个节点的右子树比父节点大，而是父节点比左子树的左右节点都大，比右子树的所有节点都小；因为没有考虑全，所以感觉自己没问题，结果调试后一直通过不了；

2、这题通过中序遍历的方式完成，仔细体会代码还能熟悉一下方法栈的调用过程；

3、另外此题还能通过中序遍历将各节点元素收集到一个数组中，然后判断改数组是否是有序的；

代码：

//通过中序遍历+递归的方式判断
class Solution {Long maxValue = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {//如果到叶子节点了，则直接返回true；if (root == null) {return true;}boolean leftFlag = isValidBST(root.left);if (root.val > maxValue) {maxValue = Long.valueOf(root.val);} else {return false;}boolean rightFlag = isValidBST(root.right);return leftFlag && rightFlag;}
}//通过中序遍历收集数组的方式判断
class Solution {public boolean isValidBST(TreeNode root) {if (root == null) {return false;}if (root.left == null && root.right == null) {return true;}List<Integer> params = new ArrayList<>();//通过中序遍历收集二叉树元素collectParams(root, params);return validListSorted(params);}public void collectParams(TreeNode node, List<Integer> params) {if (node == null) {return;}collectParams(node.left, params);//收集元素params.add(node.val);collectParams(node.right, params);}public boolean validListSorted(List<Integer> list) {int left = 0;int right = 1;while (right <= list.size()-1) {if (list.get(left) >= list.get(right)) {return false;}left++;right++;}return true;}
}