代码随想录算法训练营
—day17
文章目录
- 代码随想录算法训练营
- 前言
- 一、654.最大二叉树
- 递归法
- 递归法高效版
- 二、617.合并二叉树
- 递归法
- 迭代法
- 三、 700.二叉搜索树中的搜索
- 递归法
- 迭代法
- 四、 98. 验证二叉搜索树
- 递归法
- 总结
前言
今天是算法营的第17天，最近比较忙，题目做完了没来得及写博客，抽空补上了。
今日任务：
● 654.最大二叉树
● 617.合并二叉树
● 700.二叉搜索树中的搜索
● 98.验证二叉搜索树
一、654.最大二叉树
题目链接
文章讲解
视频讲解
最大二叉树的构建过程：
找到数组中的的最大值作为根节点，
最大值左端的剩余元素构建左子树，
最大值右端的剩余元素构建右子树。
递归法
构造二叉树一般是用前序法。
- 递归函数的参数和返回值：参数：传入数组 返回值：构造好的二叉树的根节点
- 终止条件：剩余数组大小为1，构建剩余的一个节点就退出
- 单层递归的逻辑：
用两个变量，遍历数组，记录最大值和下标。
最大值作为当前节点值，
[begin，max)以数组开头和最大值下标为区间，
递归调用函数，返回的值赋值给当前节点的左节点。
[max+1,end)以最大值下标后一位和数组结尾为区间，
递归调用函数，返回的值赋给当前节点的右节点。
/**
* 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* constructMaximumBinaryTree(vector<int>& nums) {
TreeNode* node = new TreeNode(0);
//这里没有判断数组是否为空，是因为题目写了数组大小>=1
if (nums.size() == 1) {
node->val = nums[0];
return node;
}
//找到数组中最大的值和对应的下标
int MaxNum = 0;
int index = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > MaxNum) {
MaxNum = nums[i];
index = i;
}
}
node->val = MaxNum;
//最大值的左区域，构造左子树
if (index > 0) { //保证数组大小至少为1
vector<int> vec(nums.begin(), nums.begin() + index); //左闭右开
node->left = constructMaximumBinaryTree(vec);
}
//最大值的右区域，构造右子树
if (index < nums.size() - 1) { //保证数组大小至少为1
vector<int> vec(nums.begin() + index + 1, nums.end()); //左闭右开，+1是因为要跳过node这个节点
node->right = constructMaximumBinaryTree(vec);
}
return node;
}
};
递归法高效版
其实不需要每次都构建新数组，只需要记录每次获取的最大值左右区间的下标就可以了。跟106.从中序与后序遍历序列构造二叉树一样。
另外这里的终止条件改成遇到空节点，也就是数组大小为0就终止。
所以在单次递归时就不需要再加if了
/**
* 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* traversal(int begin, int end, vector<int>& nums) {
if (begin >= end) return nullptr; //把空节点移到前面判断，下面递归就不用判断了
int index = begin;
for (int i = begin; i < end; i++) {
if (nums[i] > nums[index]) index = i;
}
TreeNode* node = new TreeNode(nums[index]);
//左闭右开 [begin, index)
node->left = traversal(begin, index, nums);
//左闭右开：[index+1, end)
node->right = traversal(index + 1, end, nums);
return node;
}
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return traversal(0, nums.size(), nums);
}
};
二、617.合并二叉树
题目链接
文章讲解
视频讲解
题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。
这道题目中涉及到回溯，因为需要把路径记录下来，处理完该节点后回退上一个节点再进入另一个节点。
递归法
思路：
- 递归函数参数以及返回值：传入两个根节点，返回合并的后的根节点
- 终止条件：传入的节点有其中一个为空，则直接返回另一个节点
- 单层处理逻辑:将最终结果保存到存入的其中一个二叉树中
- 当前节点的值相加，递归调用函数分别获取左节点和右节点。
代码如下：
/**
* 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) return root2; //如果两个都为空也没关系，结果也是返回空
if (!root2) return root1;
//用root1保存最后结果
root1->val += root2->val;//中，root1和root2同一个位置的节点值相加
root1->left = mergeTrees(root1->left, root2->left); //root1和root2同一个位置的左节点递归返回节点
root1->right = mergeTrees(root1->right, root2->right);//root1和root2同一个位置的右节点递归返回节点
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 {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (!root1) return root2; //当其中一个根节点是空的，返回另外一个根节点
if (!root2) return root1;
queue<TreeNode*> que; //用队列来存放需要处理的相邻节点
que.push(root1);
que.push(root2);
while (!que.empty()) {
TreeNode* node1 = que.front();
que.pop();
TreeNode* node2 = que.front();
que.pop();
//此处node1和node2肯定不为空
node1->val += node2->val;
//将不为空的node1,2的左右节点放入队列
if (node1->left && node2->left) {
que.push(node1->left);
que.push(node2->left);
}
if (node1->right && node2->right) {
que.push(node1->right);
que.push(node2->right);
}
//当node2的左右节点不为空，且node1左右节点为空，将node2相应节点赋值给node1相应节点
if (!node1->left && node2->left) {
node1->left = node2->left;
}
if (!node1->right && node2->right) {
node1->right = node2->right;
}
}
return root1;
}
};
三、 700.二叉搜索树中的搜索
题目链接
文章讲解
视频讲解
二叉搜索树是一个有序树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉搜索树
思路：
根据二叉搜索树的特性，不需要分什么顺序的遍历，因为二叉搜索树本身是有顺序的。
递归法
- 递归函数的参数和返回值：传入树的根节点和目标值，返回节点
- 终止条件：如果遇到空节点或者当前节点值等于目标值，返回当前节点
- 单层递归的逻辑：当前节点值小于目标值，向右递归；大于目标值，向左递归；
/**
* 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* searchBST(TreeNode* root, int val) {
//当前节点为空或者当前节点的值等于目标值则返回当前节点
if (!root || root->val == val) return root;
TreeNode* result = nullptr;
//根据二叉搜索树的特性，左节点值 < 当前节点值 < 右节点值
if (root->val > val) result = searchBST(root->left, val);
if (root->val < val) result = searchBST(root->right, val);
return result;
}
};
迭代法
代码如下：
/**
* 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* searchBST(TreeNode* root, int val) {
while (root) {
if (root->val > val) root = root->left;
else if (root->val < val) root = root->right;
else return root;
}
return nullptr;
}
};
四、 98. 验证二叉搜索树
题目链接
文章讲解
视频讲解
思路：
因为二叉搜索树的特性，左中右节点的值是递增的，关键就是验证值是否递增
递归法
- 递归函数的参数和返回值：传入树的根节点，返回bool
- 终止条件：如果遇到空节点返回true
- 单层递归的逻辑：使用中序遍历，保存最大值，如果当前节点的值没有大于保存的最大值，则返回false。否则结合左右递归的结果返回。
代码如下：
/**
* 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:
long long maxNum = LONG_MIN; //记录最大值
bool isValidBST(TreeNode* root) {
if (root == nullptr) return true; //空节点也算二叉搜索树
//二叉树的中序遍历的元素是递增，所以用中序判断是否递增可以验证二叉搜索树
bool left = isValidBST(root->left);
if (maxNum < root->val) maxNum = 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 {
public:
TreeNode* pre = nullptr;
//用节点来代替初始化最小值，避免后台题目数据中有最小值
bool isValidBST(TreeNode* root) {
if (root == nullptr) return true;
bool left = isValidBST(root->left);
if (pre && pre->val >= root->val) return false;
pre = root;
bool right = isValidBST(root->right);
return left & right;
}
};
总结
今天主要是学习了：
1.输入是数组的时候，递归的时候可以不需要重新构造新数组，只需要保存对应的下标。
2.需要同时操作两个二叉树，迭代法可以使用队列同时放入两个节点，再取两次出来做处理。
3.二叉搜索树的特性：左<中<右，中序遍历二叉搜索树会得到升序数组。
明天继续加油！
