第六章 二叉树part08

2026.03.15 02.22 第二十六天

669 修剪二叉搜索树

有一点难度。关键是了解左右第一个区间之外的节点，他们的子树可能也是符合区间要求的。

递归法：

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root == nullptr) return nullptr;if(root->val < low) {TreeNode* right = trimBST(root->right, low, high);return right;}if(root->val > high) {TreeNode* left = trimBST(root->left, low, high);return left;}root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);return root;}
};

迭代法也简单，while循环即可。

108 将有序数组转化为二叉搜索树

难度不大，但是要注意递归细节和二分的区间操作，尤其是区间边界，左闭右开和终止条件等细节。

递归法：

class Solution {
private:TreeNode* travelsal(vector<int>& nums, int begin, int end) {if(begin >= end) return nullptr;int middle = begin + (end - begin) / 2;TreeNode* cur = new TreeNode(nums[middle]);cur->left = travelsal(nums, begin, middle);cur->right = travelsal(nums, middle + 1, end);return cur; }public:TreeNode* sortedArrayToBST(vector<int>& nums) {return travelsal(nums, 0, nums.size());}
};

迭代法使用三个队列，二刷再看吧~

538 把二叉搜索树转化为累加树

相对简单

使用反中序遍历，同时利用双指针（pre）记录前一个节点的累加值

递归法：

class Solution {
private:int pre;void travelsal(TreeNode* cur) {if(cur == nullptr) return;travelsal(cur->right);cur->val += pre;pre = cur->val;travelsal(cur->left);}public:TreeNode* convertBST(TreeNode* root) {pre = 0;travelsal(root);return root;}
};

迭代法需要使用栈。