一、参考资料
最大二叉树
题目链接/文章讲解: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
合并二叉树
题目链接/文章讲解: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
二叉搜索树中的搜索
视频讲解:https://www.bilibili.com/video/BV1wG411g7sF
验证二叉搜索树
题目链接/文章讲解: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
二、LeetCode654.最大二叉树
https://leetcode.cn/problems/maximum-binary-tree/description/
示例一:
![](/i/ll/?i=img_convert/d4b6255761fce7384ee8679d4c8ac3ee.jpeg)
示例二:
![](/i/ll/?i=img_convert/01ebf459fd4c3ddd09918d84e24523a4.jpeg)
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点,其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
示例 1:
输入:nums = [3,2,1,6,0,5] 输出:[6,3,5,null,2,0,null,null,1] 解释:递归调用如下所示: - [3,2,1,6,0,5] 中的最大值是 6 ,左边部分是 [3,2,1] ,右边部分是 [0,5] 。 - [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。 - 空数组,无子节点。 - [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。 - 空数组,无子节点。 - 只有一个元素,所以子节点是一个值为 1 的节点。 - [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。 - 只有一个元素,所以子节点是一个值为 0 的节点。 - 空数组,无子节点。
示例 2:
输入:nums = [3,2,1] 输出:[3,null,2,null,1]
提示:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode() : val(0), left(nullptr), right(nullptr) {}
- * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
- * };
- */
- class Solution {
- private:
- TreeNode* constructMaxTree(vector<int>& nums, int leftBegin, int rightEnd) {
- int maxVal = nums[leftBegin];
- int index = leftBegin;
- if (leftBegin >= rightEnd) return nullptr;
- // if (nums.size() == 1) return new TreeNode(nums[0]);
- for (int i = leftBegin; i < rightEnd; i++) {
- if (nums[i] > maxVal) {
- maxVal = nums[i];
- index = i;
- }
- }
- cout << maxVal << " " << index << endl;
- TreeNode* root = new TreeNode(maxVal);
- // 左
- if (index > 0) {
- root->left = constructMaxTree(nums, leftBegin, index);
- }
- // 右
- if (index < rightEnd- 1) {
- root->right = constructMaxTree(nums, index + 1, rightEnd);
- }
- return root;
- }
- public:
- TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
- if (nums.size() == 1) {
- return new TreeNode(nums[0]);
- }
- return constructMaxTree(nums, 0, nums.size()); // 左闭右开
- }
- };
注意事项记录:
- class Solution {
- // 几点需要注意的:
- // 1. 所有区间边界问题,左闭右开
- // 2. 递归结束的条件:递归结束的条件是区间左端点的值≥区间右端点的值
- // 3. 在采用这种传下标的方法时,maxVal和index的初始化要用下标来表示,而不是默认0
- // 4. 加if判断是为了不让空节点进入递归
- private:
- TreeNode* constructMaxTree(vector<int>& nums, int leftBegin, int rightEnd) {
- int maxVal = nums[leftBegin];
- int index = leftBegin;
- if (leftBegin >= rightEnd) return NULL;
- for (int i = leftBegin; i < rightEnd; i++) {
- if (nums[i] > maxVal) {
- maxVal = nums[i];
- index = i;
- }
- }
- // cout << maxVal << " " << index << endl;
- TreeNode* root = new TreeNode(maxVal);
- // 左 // 这里加了判断是为了不让空节点进入递归
- if (index > 0) {
- root->left = constructMaxTree(nums, leftBegin, index);
- }
- // 右 // 这里加了判断是为了不让空节点进入递归
- if (index < rightEnd- 1) {
- root->right = constructMaxTree(nums, index + 1, rightEnd);
- }
- return root;
- }
- public:
- TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
- if (nums.size() == 1) {
- return new TreeNode(nums[0]);
- }
- return constructMaxTree(nums, 0, nums.size()); // 左闭右开
- }
- };
三、LeetCode617.合并二叉树
https://leetcode.cn/problems/merge-two-binary-trees/description/
示例1:
![](/i/ll/?i=img_convert/e90bef2742f0cf00bdcac176c00fdfdc.jpeg)
给你两棵二叉树: root1 和 root2 。
想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则, 不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1:
输入:root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] 输出:[3,4,5,5,4,null,7]
示例 2:
输入:root1 = [1], root2 = [1,2] 输出:[2,2]
提示:
两棵树中的节点数目在范围 [0, 2000] 内
-10^4 <= Node.val <= 10^4
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode() : val(0), left(nullptr), right(nullptr) {}
- * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
- * };
- */
- class Solution {
- // 本题旨在考察如何同步处理两个树 —— 采用前中后序遍历均可以!(代码以前序为例)
- public:
- TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
- if (root1 == NULL) return root2; // 如果root1为空,合并之后就应该是root2
- if (root2 == NULL) return root1; // 如果root2为空,合并之后就应该是root1
- // 修改了root1的数值和结构
- root1->val += root2->val; // 中
- root1->left = mergeTrees(root1->left, root2->left); // 左
- root1->right = mergeTrees(root1->right, root2->right); // 右
- return root1;
- }
- };
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode() : val(0), left(nullptr), right(nullptr) {}
- * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
- * };
- */
- class Solution {
- // 不改变root1,而是新建一棵树
- public:
- TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
- if (root1 == NULL) return root2; // 如果root1为空,合并之后就应该是root2
- if (root2 == NULL) return root1; // 如果root2为空,合并之后就应该是root1
- // 新建树
- TreeNode* root = new TreeNode(root1->val + root2->val); // 中
- root->left = mergeTrees(root1->left, root2->left); // 左
- root->right = mergeTrees(root1->right, root2->right); // 右
- return root;
- }
- };
队列迭代法:(不是很熟练——参考代码随想录)
- class Solution {
- public:
- TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
- if (t1 == NULL) return t2;
- if (t2 == NULL) return t1;
- queue<TreeNode*> que;
- que.push(t1);
- que.push(t2);
- while(!que.empty()) {
- TreeNode* node1 = que.front(); que.pop();
- TreeNode* node2 = que.front(); que.pop();
- // 此时两个节点一定不为空,val相加
- node1->val += node2->val;
- // 如果两棵树左节点都不为空,加入队列
- if (node1->left != NULL && node2->left != NULL) {
- que.push(node1->left);
- que.push(node2->left);
- }
- // 如果两棵树右节点都不为空,加入队列
- if (node1->right != NULL && node2->right != NULL) {
- que.push(node1->right);
- que.push(node2->right);
- }
- // 当t1的左节点 为空 t2左节点不为空,就赋值过去
- if (node1->left == NULL && node2->left != NULL) {
- node1->left = node2->left;
- }
- // 当t1的右节点 为空 t2右节点不为空,就赋值过去
- if (node1->right == NULL && node2->right != NULL) {
- node1->right = node2->right;
- }
- }
- return t1;
- }
- };
四、LeetCode700.二叉搜索树中的搜索
https://leetcode.cn/problems/search-in-a-binary-search-tree/description/
示例1:
![](/i/ll/?i=img_convert/d28cc311e8acc18ecac1985d51ecc26c.jpeg)
示例2:
![](/i/ll/?i=img_convert/dff0ec398263871394d9f5a36ba09488.jpeg)
给定二叉搜索树(BST)的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。
示例 1:
输入:root = [4,2,7,1,3], val = 2 输出:[2,1,3]
示例 2:
输入:root = [4,2,7,1,3], val = 5 输出:[]
提示:
数中节点数在 [1, 5000] 范围内
1 <= Node.val <= 10^7
root 是二叉搜索树
1 <= val <= 10^7
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode() : val(0), left(nullptr), right(nullptr) {}
- * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
- * };
- */
- class Solution {
- // version1: 递归法
- public:
- TreeNode* searchBST(TreeNode* root, int val) {
- TreeNode* res = NULL;
- if (root == NULL || root->val == val) return root;
- if (val < root->val) res = searchBST(root->left, val);
- if (val > root->val) res = searchBST(root->right, val);
- return res;
- }
- };
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode() : val(0), left(nullptr), right(nullptr) {}
- * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
- * };
- */
- class Solution {
- // version2: 继续递归(简化版)
- public:
- TreeNode* searchBST(TreeNode* root, int val) {
- if (root == NULL || root->val == val) return root;
- if (root->val > val) return searchBST(root->left, val);
- if (root->val < val) return searchBST(root->right, val);
- return NULL;
- }
- };
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode() : val(0), left(nullptr), right(nullptr) {}
- * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
- * };
- */
- class Solution {
- // version3: 迭代法
- public:
- TreeNode* searchBST(TreeNode* root, int val) {
- while (root != NULL) {
- if (root->val > val) root = root->left;
- else if (root->val < val) root = root->right;
- else return root;
- }
- return NULL;
- }
- };
因为二叉搜索树的有序性,遍历的时候要比普通二叉树简单很多。
五、LeetCode98.验证二叉搜索树
https://leetcode.cn/problems/validate-binary-search-tree/description/
回顾一下中序遍历的迭代法写法
// https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html#%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86-%E8%BF%AD%E4%BB%A3%E6%B3%95
示例1:
![](/i/ll/?i=img_convert/431ba841a741b08ec5d473c69e0e0b5f.jpeg)
示例2:
![](/i/ll/?i=img_convert/048fd5ef991dc77813bdfecb02ec8253.jpeg)
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3] 输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。
提示:
树中节点数目范围在[1, 104] 内
-2^31 <= Node.val <= 2^31 - 1
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode() : val(0), left(nullptr), right(nullptr) {}
- * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
- * };
- */
- class Solution {
- // version1:直接比较(为了满足了测试样例而定义初始值)
- public:
- long long maxVal = LONG_MIN; // 注意:这个最小值应该写到递归函数外面,不然每次递归子树时都会重新进入
- bool isValidBST(TreeNode* root) {
- if (root == NULL) return true;
- bool left = isValidBST(root->left); // 左
- if (root->val > maxVal) {
- maxVal = root->val; // 中
- } else {
- return false;
- }
- bool right = isValidBST(root->right); //右
- return left && right;
- }
- };
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode() : val(0), left(nullptr), right(nullptr) {}
- * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
- * };
- */
- class Solution {
- // version2:双指针优化 —— 需要注意的是 判断前一个节点≥当前节点时,返回false,而不是仅大于
- public:
- TreeNode* pre = NULL; // pre记录前一个节点的值
- bool isValidBST(TreeNode* root) {
- if (root == NULL) return true;
- bool left = isValidBST(root->left); // 左
- if (pre != NULL && pre->val >= root->val) return false;
- pre = root;
- bool right = isValidBST(root->right); //右
- return left && right;
- }
- };
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode() : val(0), left(nullptr), right(nullptr) {}
- * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
- * };
- */
- class Solution {
- // version 3: 迭代法模拟二叉树中序遍历
- public:
- bool isValidBST(TreeNode* root) {
- stack<TreeNode*> st;
- TreeNode* pre = NULL; // 记录前一个节点
- TreeNode* cur = root;
- while (cur != NULL || !st.empty()) {
- if (cur != NULL) {
- st.push(cur);
- cur = cur->left; // 左
- } else {
- cur = st.top(); // 中
- st.pop();
- if (pre != NULL && pre->val >= cur->val) {
- return false;
- } else {
- pre = cur;
- }
- cur = cur->right; // 右
- }
- }
- return true;
- }
- };
我写的版本
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode() : val(0), left(nullptr), right(nullptr) {}
- * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
- * };
- */
- class Solution {
- // version 4: 我写的迭代法模拟二叉树中序遍历
- // https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html#%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86-%E8%BF%AD%E4%BB%A3%E6%B3%95
- public:
- bool isValidBST(TreeNode* root) {
- stack<TreeNode*> st;
- TreeNode* pre = NULL; // 记录前一个节点
- TreeNode* cur = root;
- while (cur != NULL || !st.empty()) {
- if (cur != NULL) {
- st.push(cur);
- cur = cur->left;
- }
- if (cur != NULL) {
- st.push(cur);
- cur = cur->left; // 左
- } else {
- cur = st.top(); // 中
- st.pop();
- if (pre != NULL && pre->val >= cur->val) {
- return false;
- } else {
- pre = cur;
- }
- cur = cur->right; // 右
- }
- }
- return true;
- }
- };
陷阱1
不能单纯的比较左节点小于中间节点,右节点大于中间节点就完事了。
陷阱2
样例中最小节点 可能是int的最小值,如果这样使用最小的int来比较也是不行的。
此时可以初始化比较元素为longlong的最小值。
进一步解决陷阱2,引入了version2的代码,通过双指针优化
总结:
做到现在已经能够看完视频独立写出代码了,下一步通过复习希望能熟练掌握解题的思路,还有什么类型的题用前序遍历,什么类型的题用后序遍历,什么类型的题用中序遍历,什么类型的题不用考虑遍历顺序等等。
参考以下这个博主的解答:
https://blog.csdn.net/weixin_44561338/article/details/107946716
前序遍历(中左右)
第一次访问就输出数据
适合静态访问
中序遍历(左中右)
对于二分搜索树,输出结果是有序的
适合顺序输出结果
后序遍历(左右中)
对节点操作时必访问过其子节点
适合进行破坏性操作(删除节点)
刷题加油鸭~~
标签:right,TreeNode,val,int,二叉,搜索,二叉树,root,left From: https://www.cnblogs.com/ucaszym/p/17093512.html