算法刷题Day 23 修剪二叉搜索树+将有序数组转换为二叉搜索树+把二叉搜索树转换为累加树

这篇具有很好参考价值的文章主要介绍了算法刷题Day 23 修剪二叉搜索树+将有序数组转换为二叉搜索树+把二叉搜索树转换为累加树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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. 把二叉搜索树转换为累加树

其实就是以右->中->左的顺序来处理二叉树

每次将当前节点加上上一次访问节点的新值

能想到保存前一次访问节点的新值,这道题就很容易解决

递归

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode108. 将有序数组转换为二叉搜索树

    108. 将有序数组转换为二叉搜索树 一、题目 给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 示例 1: 示例 2: 提示: 1 = nums.

    2024年02月11日
    浏览(28)
  • leetcode 108. 将有序数组转换为二叉搜索树

            由数组构造二叉搜索树地问题,本题可以借鉴从中序与后序遍历序列构造二叉树 这道题,这类题 本质就是寻找分割点,分割点作为当前节点,然后递归左区间和右区间 。         下面直接看代码:

    2024年02月16日
    浏览(33)
  • 力扣日记1.14-【二叉树篇】108. 将有序数组转换为二叉搜索树

    日期:2023.1.14 参考:代码随想录、力扣 题目描述 难度:简单 给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 示例 1: 输入:

    2024年02月01日
    浏览(36)
  • LeetCode 热题 100 JavaScript--108. 将有序数组转换为二叉搜索树

    给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 提示: 1 = nums.length = 104 -104 = nums[i] = 104 nums 按 严格递增 顺序排列

    2024年02月14日
    浏览(40)
  • 算法刷题Day 20 最大二叉树+合并二叉树+二叉搜索树中的搜索+验证二叉搜索树

    递归 递归 迭代 递归 迭代 遇到两个坑的地方: 递归的时候,不能光验证左子树的根节点小于当前根节点,右子树的根节点大于但当前根节点,别忘了左子树上的每一个节点都要求比根节点要小,右子树上的每一个节点都要求比根节点大。 根节点跟左(右)子树中的某一个节

    2024年02月16日
    浏览(43)
  • 【算法刷题day20】Leetcode:654. 最大二叉树、617.合并二叉树、700. 二叉搜索树中的搜索、98.验证二叉搜索树

    草稿图网站 java的Deque 题目: 654. 最大二叉树 解析: 代码随想录解析 解题思路 NLR的建树 代码 总结 暂无 题目: 617.合并二叉树 解析: 代码随想录解析 解题思路 如果都为root1, root2都为空,返回null;如果root1为空,root2不为空,返回root2;如果roo1不为空,root2为空,返回root

    2024年04月10日
    浏览(38)
  • 算法刷题Day 21 二叉搜索树的最小绝对差+二叉搜索树中的众数+二叉树的最近公共祖先

    递归 递归中保存前一个节点的指针的方法,需要再学习,巩固一下 迭代 一下子就想到的方法:遍历一遍二叉搜索树,把各个节点的值存进哈希表里(节点值——键,出现频率——值),再遍历哈希表找众数 一般方法 既然是二叉搜索树,中序遍历就是有序的。有序的话,我

    2024年02月16日
    浏览(43)
  • 算法刷题Day 22 二叉搜索树的最近公共祖先+二叉搜索树中的插入操作+删除二叉搜索树中的节点

    根据二叉搜索树的性质,相比普通二叉树可以极大程度的简化代码,作为公共祖先其值一定在两个给定节点值之间,从树根往下遍历,第一次出现两个给定节点值之间的值,那个节点即为最近公共祖先(为什么是最近不是最远?根节点一般为最远,第一次出现的值处于两个给

    2024年02月17日
    浏览(43)
  • 【算法刷题day22】Leetcode:235. 二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 50.删除二叉搜索树中的节点

    文档链接:[代码随想录] 题目链接:235. 二叉搜索树的最近公共祖先 题目: 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深

    2024年04月13日
    浏览(40)
  • 将有序数组转换为二叉树

    md这个破CSDN模板怎么没了,编辑器也死难用,气死 给你一个整数数组  nums  ,其中元素已经按  升序  排列,请你将其转换为一棵  高度平衡  二叉搜索树。 高度平衡  二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 示例 1: 示例 2:

    2024年02月05日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包