Day 23 二叉树
669. 修剪二叉搜索树
递归
好神奇,完全凭感觉写,感觉应该过不了,结果就过了
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (!root) return nullptr;
if (root->val < low)
{
return trimBST(root->right, low, high);
}
else if (root->val > high)
{
return trimBST(root->left, low, high);
}
else
{
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
}
return root;
}
};
具体是什么原理可以参考代码随想录的讲解
108. 将有序数组转换为二叉搜索树
递归
class Solution {
TreeNode *build(const vector<int> &nums, int left, int right)
{
if (left >= right) return nullptr;
int mid = left + (right - left) / 2;
TreeNode *node = new TreeNode(nums[mid]);
node->left = build(nums, left, mid);
node->right = build(nums, mid + 1, right);
return node;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, nums.size());
}
};
迭代
使用三个队列来处理(感觉用三个栈也可以)
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (!nums.size()) return nullptr;
queue<TreeNode*> que;
queue<int> leftSide;
queue<int> rightSide;
TreeNode *root = new TreeNode(0);
que.push(root);
leftSide.push(0);
rightSide.push(nums.size());
while (!que.empty())
{
TreeNode *cur = que.front();
que.pop();
int left = leftSide.front();
leftSide.pop();
int right = rightSide.front();
rightSide.pop();
int mid = left + (right - left) / 2;
cur->val = nums[mid];
if (left < mid)
{
cur->left = new TreeNode(0);
que.push(cur->left);
leftSide.push(left);
rightSide.push(mid);
}
if (right > mid + 1)
{
cur->right = new TreeNode(0);
que.push(cur->right);
leftSide.push(mid + 1);
rightSide.push(right);
}
}
return root;
}
};
538. 把二叉搜索树转换为累加树
其实就是以右->中->左的顺序来处理二叉树
每次将当前节点加上上一次访问节点的新值
能想到保存前一次访问节点的新值,这道题就很容易解决文章来源:https://www.toymoban.com/news/detail-618217.html
递归
class Solution {
int preSum = 0;
void traversal(TreeNode *root)
{
if (!root) return;
traversal(root->right);
root->val = root->val + preSum;
preSum = root->val;
traversal(root->left);
}
public:
TreeNode* convertBST(TreeNode* root) {
// 右中左
if (!root) return nullptr;
preSum = 0;
traversal(root);
return root;
}
};
迭代
中序遍历迭代方法修改一下左右节点的顺序,就能解决这个问题了文章来源地址https://www.toymoban.com/news/detail-618217.html
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
if (!root) return nullptr;
stack<TreeNode*> stk;
TreeNode *cur = root;
int lastSum = 0;
while (cur || !stk.empty())
{
if (cur)
{
stk.push(cur);
cur = cur->right;
}
else
{
cur = stk.top();
stk.pop();
cur->val += lastSum;
lastSum = cur->val;
cur = cur->left;
}
}
return root;
}
};
到了这里,关于算法刷题Day 23 修剪二叉搜索树+将有序数组转换为二叉搜索树+把二叉搜索树转换为累加树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!