算法训练营第二十五天 | LeetCode 669 修剪二叉树、

本文主要是介绍算法训练营第二十五天 | LeetCode 669 修剪二叉树、，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode 669 修剪二叉树

这题用层序遍历+双指针删除不符合条件的节点即可。具体是要用到一个虚拟根节点，双指针中prev指针每次指向队列顶元素，cur指针先指向prev左子节点，用循环去除这个位置上不符合条件的节点并连上继承节点，内部就是一个删除节点的操作。后指向prev右子节点，重复上述操作。此时若prev左子节点和右子节点仍不为空，则将它们入队列继续执行上述过程即可。

后面遇到一个栈溢出错误，上网查了资料知道是力扣隐藏的判题代码求我们将被剪的节点置空，所以又将每次去除后的节点的左子节点和右子节点都赋为nullptr了。

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {TreeNode* virtualRoot = new TreeNode(0);virtualRoot->left = root;queue<TreeNode*> myque;myque.push(virtualRoot);while (!myque.empty()) {int num = myque.size();while (num--) {TreeNode* prev = myque.front();TreeNode* cur = prev->left;while (cur && !(cur->val >= low && cur->val <= high)) {if (!cur->left && !cur->right) prev->left = nullptr;else if (!cur->left) {prev->left = cur->right; cur->right = nullptr;} else if (!cur->right) {prev->left = cur->left;cur->left = nullptr;}else {TreeNode* temp = cur->right;while (temp->left) temp = temp->left;temp->left = cur->left;prev->left = cur->right;cur->left = nullptr;cur->right = nullptr;}cur = prev->left;}if (prev->left) myque.push(prev->left);cur = prev->right;while (cur && !(cur->val >= low && cur->val <= high)) {if (!cur->left && !cur->right) prev->right = nullptr;else if (!cur->left) prev->right = cur->right;else if (!cur->right) prev->right = cur->left;else {TreeNode* temp = cur->left;while (temp->right) temp = temp->right;temp->right = cur->right;prev->right = cur->left;}cur->left = nullptr;cur->right = nullptr;cur = prev->right;}if (prev->right) myque.push(prev->right);myque.pop();}}return virtualRoot->left;}
};

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

用递归 + 二分查找的思路来处理就行了。

代码如下：

class Solution {
private:TreeNode* binaryBuild(vector<int>& nums , int l, int r) {if (l > r) return nullptr;int mid = (l + r) / 2;TreeNode* newNode = new TreeNode(nums[mid]);newNode->left = binaryBuild(nums, l, mid - 1);newNode->right = binaryBuild(nums, mid + 1, r);return newNode;}
public:TreeNode* sortedArrayToBST(vector<int>& nums) {return binaryBuild(nums, 0, nums.size() - 1);}
};

LeetCode 538 把二叉搜索树转换为累加树

迭代法。按照右中左的顺序用一个变量依次累加每个节点的值，当到达一个节点时，先把该变量加上该节点的值，之后将该节点的值赋为该变量的值，即可满足条件。

代码如下：

class Solution {
public:TreeNode* convertBST(TreeNode* root) {TreeNode* cur = root;stack<TreeNode*> mysta;int sum = 0;while (cur || !mysta.empty()) {while (cur) {mysta.push(cur);cur = cur->right;}cur = mysta.top();sum += cur->val;cur->val = sum;mysta.pop();cur = cur->left;}return root;}
};

这篇关于算法训练营第二十五天 | LeetCode 669 修剪二叉树、的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---