代码随想录训练营第二十天 | (递归法实现)最大二叉树&&合并二叉树&&二叉搜索树中的搜索&&*验证二叉搜索树
654.最大二叉树
文章:19. 最大二叉树
题目:654. 最大二叉树
视频:又是构造二叉树,又有很多坑!| LeetCode:654.最大二叉树_哔哩哔哩_bilibili
【思路】
构造二叉树类型的题目,我们都使用前序遍历对二叉树进行构造。
先构造中间节点,再构造左子树,最构造右子树
递归
1.确递归函数的参数和返回值
2.确定终止条件
- 当传入的数组大小为1的时候,说明遍历到了叶子节点
- 那么应该定义一个新节点,把这个数组的数值赋给新的节点,然后返回这个节点。
3.确定单层递归的逻辑
- 先找到数组中最大值和对应的下标,最大的值构造根节点,下标用来下一步分割数组。
- 最大值所在的下标左区间 构造左子树
- 最大值所在的下标右区间 构造右子树
- Java实现
1 | class Solution { |
- Go实现
1 | func constructMaximumBinaryTree(nums []int) *TreeNode { |
617.合并二叉树
文章:21. 合并二叉树
题目:617. 合并二叉树
视频:一起操作两个二叉树?有点懵!| LeetCode:617.合并二叉树_哔哩哔哩_bilibili
【思路】
使用前序遍历。一开始通过root1
和root2
是否为空作为判断条件,有效的解决了出现如果root1
或root2
为空&&root1==null &&root2==null
,然后通过递归来获取左子树和右子树。
- Java实现
1 | class Solution { |
- Go实现
1 | func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode { |
700.二叉搜索树中的搜索
【思路】
二叉搜索树是一个有序树
- 若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值
- 若它的右子树不为空,则柚子树上所有系欸但的值均大于它的根节点的值
- 它的左、右子树也分别为二叉搜索树
需要新建一个变量来承接递归后的值,而不是修改原来的root节点。
- Java实现
1 | class Solution { |
- Go实现
1 | func searchBST(root *TreeNode, val int) *TreeNode { |
23.验证二叉搜索树
文章:23. 验证二叉搜索树
题目:98. 验证二叉搜索树
视频:你对二叉搜索树了解的还不够! | LeetCode:98.验证二叉搜索树_哔哩哔哩_bilibili
【思路】
误区:只判断了 if root.Left.Val >= root.Val || root.Right.Val < root.Val
,而忽略了二叉搜索树的根节点也大于左子树的全部节点,小于右子树的全部节点。
Java实现(不是很理解
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
TreeNode max;
public boolean isValidBST(TreeNode root) {
if(root ==null)return true;
boolean left= isValidBST(root.left);
if(!left)return false;
if(max!=null && root.val <= max.val){
return false;
}
max = root;
boolean right = isValidBST(root.right);
return right;
}
}Go实现
1 | func isValidBST(root *TreeNode) bool { |
【算法总结】
最大二叉树:构造二叉树类型的题目,我们都使用前序遍历对二叉树进行构造。
合并二叉树:递归实现
二叉搜索树中的搜索:递归实现,需要新建一个变量来承接递归后的值,而不是修改原来的root节点。
验证二叉搜索树:
- 误区:只判断了
if root.Left.Val >= root.Val || root.Right.Val < root.Val
,而忽略了二叉搜索树的 - 但是不是很理解java的解法是什么意思,希望后面复盘的时候可以再看一遍!
- 误区:只判断了
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 林重笑!