title: 有序数组、BST、l累加树的转换
📃 题目一描述
题目链接：108. 将有序数组转换为二叉搜索树
🔔 解题思路
解法一：递归法
符合高度平衡，那么每次取中间值作为节点，将数组分成左右两半，作为左右子树即可；
要明确：如何处理边界问题
class Solution {
public:
TreeNode* sortedArrayToBST(vector& nums) {
return toBST(nums, 0, nums.size() - 1);
}
TreeNode* toBST(vector& nums, int left, int right) {
if (left > right) return nullptr; // 处理不存在的边界情况
if (right == left) return new TreeNode(nums[right]); // 处理只剩下一个节点的边界情况
int mid = (right + left) / 2;
TreeNode* cur = new TreeNode(nums[mid]);
cur->left = toBST(nums, left, mid - 1);
cur->right = toBST(nums, mid + 1, right);
return cur;
}
};
解法二：迭代法
和递归法一样，只是用迭代重现一遍，思路可以自己好好思考，采用思想就是一种自上而下的构造，不断分割的过程；
class Solution {
public:
TreeNode* sortedArrayToBST(vector& nums) {
if (nums.size() == 0) return nullptr;
// 采用自上而下的构造
stack nodeCur; // 存放遍历到的节点
stack leftCur; // 存放遍历到的左坐标
stack rightCur; // 存放遍历到右坐标
TreeNode* root = new TreeNode(0);
nodeCur.push(root);
leftCur.push(0);
rightCur.push(nums.size() - 1);
while (!nodeCur.empty()) {
TreeNode* cur = nodeCur.top(); nodeCur.pop();
int left = leftCur.top(); leftCur.pop();
int right = rightCur.top(); rightCur.pop();
int mid = (right + left) >> 1;
cur->val = nums[mid]; // 赋予真正的值
// 存在左边子树， 进行构造
if (left left = new TreeNode(0);
nodeCur.push(cur->left);
leftCur.push(left);
rightCur.push(mid - 1);
}
// 存在右子树， 进行构造
if (right >= mid + 1) {
cur->right = new TreeNode(0);
nodeCur.push(cur->right);
leftCur.push(mid + 1);
rightCur.push(right);
}
}
return root;
}
};
💥 复杂度分析
- 时间复杂度：O(n);
- 空间复杂度：O(1);不考虑函数调用的空间开销
📃 题目二描述
题目链接：538. 把二叉搜索树转换为累加树
🔔 解题思路
解法一：递归法
本题较简单，主要思考如何实现从大到小遍历，其次是用一个全局变量记录所遍历节点的累加和即可；
class Solution {
public:
int sum = 0;
TreeNode* convertBST(TreeNode* root) {
if (root == nullptr) return nullptr;
// 采用右中左遍历
root->right = convertBST(root->right);
sum += root->val; // 记录遍历到的节点的累加和
root->val = sum; // 更新当前节点
root->left = convertBST(root->left);
return root;
}
};
解法二：迭代法
主要要解决的问题也是上面讲的两个，采用栈解决从大到小遍历的问题；看代码：
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
if (root == nullptr) return nullptr;
stack st;
TreeNode* cur = root;
int sum = 0;
while (cur || !st.empty()) {
if (cur) {
st.push(cur);
cur = cur->right; // 先遍历大的值; 右
}
else {
cur = st.top(); st.pop(); // 中
sum += cur->val;
cur->val = sum;
cur = cur->left; // 再遍历小的， 左
}
}
return root;
}
};
💥 复杂度分析
- 时间复杂度：O(n);
- 空间复杂度：O(1);
Original: https://www.cnblogs.com/D-booker/p/16366325.html
Author: D-booker
Title: 20. 有序数组、BST、l累加树的转换
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/713331/
转载文章受原作者版权保护。转载请注明原作者出处！