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做题思路:
构造树一般采用的是前序遍历,因为先构造中间节点,然后递归构造左子树和右子树。当递归遍历的时候,如果传入的数组大小为1,说明遍历到了叶子节点了。
- 先要找到数组中最大的值和对应的下标, 最大的值构造根节点,下标用来下一步分割数组。
- 最大值所在的下标左区间 构造左子树
- 最大值所在的下标右区间 构造右子树
每次分隔不用定义新的数组,而是通过下标索引直接在原数组上操作。
本题代码:
1 class Solution { 2 private: 3 // 在左闭右开区间[left, right),构造二叉树 4 TreeNode* traversal(vector<int>& nums, int left, int right) { 5 if (left >= right) return nullptr; //区间要合法 6 7 // 分割点下标:maxValueIndex 8 int maxValueIndex = left; 9 for (int i = left + 1; i < right; ++i) { 10 if (nums[i] > nums[maxValueIndex]) maxValueIndex = i; 11 } 12 13 TreeNode* root = new TreeNode(nums[maxValueIndex]); //中 14 15 // 左闭右开:[left, maxValueIndex) 16 root->left = traversal(nums, left, maxValueIndex); //左 17 18 // 左闭右开:[maxValueIndex + 1, right) 19 root->right = traversal(nums, maxValueIndex + 1, right); //右 20 21 return root; 22 } 23 public: 24 TreeNode* constructMaximumBinaryTree(vector<int>& nums) { 25 return traversal(nums, 0, nums.size()); //传入数组和数组区间 26 } 27 };
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
做题思路:
两个树的根,左子树,右子树相加,
因为是传入了两个树,那么就有两个树遍历的节点 t1 和 t2,如果t1 == NULL 了,两个树合并就应该是 t2 了(如果t2也为NULL也无所谓,合并之后就是NULL)。反过来如果 t2 == NULL,那么两个数合并就是 t1(如果t1也为NULL也无所谓,合并之后就是NULL)。
这里我们重复利用一下t1这个树,t1就是合并之后树的根节点(就是修改了原来树的结构)。
接下来t1 的左子树是:合并 t1左子树 t2左子树之后的左子树。
t1 的右子树:是 合并 t1右子树 t2右子树之后的右子树。最终t1就是合并之后的根节点。
本题代码:
1 TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { 2 if (t1 == NULL) return t2; // 如果t1为空,合并之后就应该是t2 3 if (t2 == NULL) return t1; // 如果t2为空,合并之后就应该是t1 4 // 修改了t1的数值和结构 5 t1->val += t2->val; // 中 6 t1->left = mergeTrees(t1->left, t2->left); // 左 7 t1->right = mergeTrees(t1->right, t2->right); // 右 8 return t1; 9 }
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
做题思路:
二叉搜索树是一个有序树:
- 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
- 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
- 它的左、右子树也分别为二叉搜索树
因为二叉搜索树的节点是有序的,所以可以有方向的去搜索。
如果root->val > val,搜索左子树,如果root->val < val,就搜索右子树,最后如果都没有搜索到,就返回NULL。
本题代码:
1 TreeNode* searchBST(TreeNode* root, int val) { 2 if (root == NULL || root->val == val) return root; 3 TreeNode* result = NULL; 4 if (root->val > val) result = searchBST(root->left, val); 5 if (root->val < val) result = searchBST(root->right, val); 6 return result; 7 }
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
做题思路:
要知道中序遍历下,输出的二叉搜索树节点的数值是有序序列。有了这个特性,验证二叉搜索树,就相当于变成了判断一个序列是不是递增的了。
可以递归中序遍历将二叉搜索树转变成一个数组,然后只要比较一下,这个数组是否是有序的,注意二叉搜索树中不能有重复元素。
关于注意事项看卡哥视频和文章。
本题代码:
1 class Solution { 2 private: 3 vector<int> vec; 4 void traversal(TreeNode* root) { //中序遍历 5 if (root == NULL) return; 6 traversal(root->left); 7 vec.push_back(root->val); // 将二叉搜索树转换为有序数组 8 traversal(root->right); 9 } 10 public: 11 bool isValidBST(TreeNode* root) { 12 vec.clear(); // 不加这句在leetcode上也可以过,但最好加上 13 traversal(root); 14 for (int i = 1; i < vec.size(); i++) { 15 // 注意要小于等于,搜索树里不能有相同元素 16 if (vec[i] <= vec[i - 1]) return false; 17 } 18 return true; 19 } 20 };
标签:val,t2,t1,搜索,二叉树,二叉,root From: https://www.cnblogs.com/romantichuaner/p/17637034.html