算法训练营day20(二叉树06:最大二叉树,合并二叉树,搜索二叉树,验证搜索二叉树)

第六章 二叉树 part06
今日内容 ● 654.最大二叉树 
● 617.合并二叉树 
● 700.二叉搜索树中的搜索 
● 98.验证二叉搜索树 详细布置 654.最大二叉树 又是构造二叉树，昨天大家刚刚做完 中序后序确定二叉树，今天做这个 应该会容易一些， 先看视频，好好体会一下 为什么构造二叉树都是 前序遍历 题目链接/文章讲解：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  617.合并二叉树 这次是一起操作两个二叉树了， 估计大家也没一起操作过两个二叉树，也不知道该如何一起操作，可以看视频先理解一下。 优先掌握递归。题目链接/文章讲解：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  700.二叉搜索树中的搜索 递归和迭代 都可以掌握以下，因为本题比较简单， 了解一下 二叉搜索树的特性题目链接/文章讲解: 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   98.验证二叉搜索树 遇到 搜索树，一定想着中序遍历，这样才能利用上特性。 但本题是有陷阱的，可以自己先做一做，然后在看题解，看看自己是不是掉陷阱里了。这样理解的更深刻。题目链接/文章讲解：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  
往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 休息 
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY 
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr 
●day 19 休息

day20

最大二叉树

递归法

 class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {//定义函数返回rootreturn construct(nums, 0,nums.length);//左闭右开}private TreeNode construct( int[] nums,int leftindex, int rightindex){//先写出递归条件,也就是数组遍历到最后if(rightindex <= leftindex) return null;if(rightindex - leftindex == 1) return new TreeNode(nums[leftindex]);//写单层逻辑//构造root节点并赋值int maxval = nums[leftindex];//初始化int maxvalindex = leftindex;for( int i = leftindex + 1; i<rightindex; i++){if(nums[i] > maxval){maxval = nums[i];maxvalindex = i;}}//根据max构造rootTreeNode root = new TreeNode(maxval);//前序遍历,有了当前节点再往下连子节点root.left = construct(nums, leftindex,maxvalindex);root.right = construct(nums, maxvalindex + 1,rightindex);return root;//单层逻辑出递归}}

---

合并二叉树

迭代法

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

---

搜索二叉树

递归法

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

---

验证二叉搜索树

递归法

 class Solution {long maxval = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if( root == null ){return true;}boolean left = isValidBST(root.left);if(maxval < root.val) maxval = root.val;else return false;boolean right = isValidBST(root.right);//中序遍历,如果在递归左子树之前就已经更新了 maxval，那么左子树的有效性检查会失败，因为它会试图用更新后的 maxval 与左子树的节点值进行比较，而不再是根节点的合法值。return left && right;}}​//为了防止二叉树中出现Long.MIN_VALUE;可以用节点保存上一个节点的数值class Solution {TreeNode pre = null;public boolean isValidBST(TreeNode root) {if( root == null ){return true;}boolean left = isValidBST(root.left);if(pre == null || pre.val < root.val) pre = root;else return false;boolean right = isValidBST(root.right);return left && right;}}

---

感谢大佬分享:

代码随想录-算法训练营day20【二叉树06：最大二叉树、合并二叉树、二叉搜索树中的搜索、验证二叉搜索树】-CSDN博客