asp.net网站开发简介,开发小程序用什么软件写代码,nginx网站开发,网业安全防护如何关闭很久没有刷算法题了#xff0c;又荒废了#xff0c;习惯还得保持啊#xff0c;希望能坚持一天1~2道题。 文章目录 二叉树32. 将有序数组转换为二叉搜索树33. 把二叉搜索树转换为累加树 二叉树
32. 将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树 思路…很久没有刷算法题了又荒废了习惯还得保持啊希望能坚持一天1~2道题。 文章目录 二叉树32. 将有序数组转换为二叉搜索树33. 把二叉搜索树转换为累加树 二叉树
32. 将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树 思路 有序数组要生成普通二叉树只需要简单的一长溜就可以了。所以题目要求生成平衡二叉树。要平衡就要左右子树的节点数最多相差1自然而然从数组的中间划分为左右子树就显得很容易。 方法1 递归法 递归的思路很清晰对左右区间递归构造二叉搜索树即可。 class Solution {
public:TreeNode* sortedArrayToBST(vectorint nums) {TreeNode *root Transfer(nums, 0, nums.size() - 1);return root;}private:TreeNode* Transfer(vectorint nums, int left, int right) {if (left right) return nullptr;int mid left ((right - left)1);TreeNode *root new TreeNode(nums[mid]);root-left Transfer(nums, left, mid - 1);root-right Transfer(nums, mid 1, right);return root;}
};方法2迭代法 同递归法的思路只不过要利用队列存储当前处理区间的当前处理节点。 class Solution {
public:TreeNode* sortedArrayToBST(vectorint nums) {if (nums.size() 0) return nullptr;TreeNode *root new TreeNode(0);queueTreeNode * nodeQue; // 栈顶是当前处理到的节点queueint leftQue; // 存当前处理区间的左边界queueint rightQue; // 存当前处理区间的有边界nodeQue.push(root); // 初始处理节点是根节点leftQue.push(0); // 初始左边界是 0rightQue.push(nums.size() - 1); // 初始右边界while (!nodeQue.empty()) {TreeNode *curNode nodeQue.front(); nodeQue.pop();int left leftQue.front(); leftQue.pop();int right rightQue.front(); rightQue.pop();int mid left ((right - left) 1);curNode-val nums[mid];// 先处理左区间if (left mid) {curNode-left new TreeNode(0);nodeQue.push(curNode-left);leftQue.push(left);rightQue.push(mid - 1);}// 再处理右区间if (right mid) {curNode-right new TreeNode(0);nodeQue.push(curNode-right);leftQue.push(mid 1);rightQue.push(right);}}return root;}
};33. 把二叉搜索树转换为累加树
538. 把二叉搜索树转换为累加树 思路 二叉搜索树变成累加树题干说的听抽象的看不太懂观察样例可以看出根节点值是自身和右子树的累加和左子节点是自身和根节点新值的累加。其实就是得到后续遍历的结果再从左向右依次累加。 在遍历过程中处理需要记录一个 pre 值表示前一个节点的值方便做累加。 方法1递归法
class Solution {
public:TreeNode* convertBST(TreeNode* root) {pre 0;Transfer(root);return root;}private:int pre 0;void Transfer(TreeNode* root) {if (root nullptr) return ;Transfer(root-right); // 右// 中root-val pre;pre root-val;Transfer(root-left); // 左}
};方法2迭代法 典型的后续遍历模板 class Solution {
public:TreeNode* convertBST(TreeNode* root) {Transfer(root);return root;}private:void Transfer(TreeNode* root) {int pre 0;stackTreeNode * stk;TreeNode *cur root;while (cur ! nullptr || !stk.empty()) {if (cur ! nullptr) { // 右stk.push(cur);cur cur-right;} else {// 中cur stk.top(); stk.pop();cur-val pre;pre cur-val;cur cur-left; // 左}}}
};
