LeetCode 热题 100 | 二叉树(中下)

这篇具有很好参考价值的文章主要介绍了LeetCode 热题 100 | 二叉树(中下)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1  基础知识

1.1  队列 queue

1.2  栈 stack

1.3  常用数据结构

1.4  排序

2  98. 验证二叉搜索树

3  230. 二叉搜索树中第 K 小的元素

4  199. 二叉树的右视图


菜鸟做题忘了第几周,躺平过了个年TT

1  基础知识

1.1  队列 queue
  1. queue<type> q:定义一个参数类型为 type 的队列
  2. q.push(variable):在队尾插入一个元素
  3. q.pop():删除队列第一个元素
  4. q.size():返回队列中元素个数
  5. q.empty():如果队列空则返回 true
  6. q.front():返回队列中的第一个元素
  7. q.back():返回队列中最后一个元素
1.2  栈 stack
  1. stack<type> s:定义一个参数类型为 type 的栈
  2. s.push(variable):压栈,无返回值
  3. s.emplace():压栈,无返回值(参见原文)
  4. s.pop():栈顶元素出栈,不返回元素,无返回值
  5. s.top():返回栈顶元素,该元素不出栈
  6. s.empty():判断栈是否为空,是返回 true
  7. s.size():返回栈中元素数量

参考博客:C++ 栈(stack)使用简述

1.3  常用数据结构
  • vector<type> v + push_back
  • unordered_set<type> s + insert
  • unordered_map<type, type> m
1.4  排序

总是忘记如何调用 sort()。。。

假设 vals 是一个容器。sort() 没有返回值,vals 里面就已经是排好的顺序了。

sort(vals.begin(), vals.end())

2  98. 验证二叉搜索树

题眼:

  • 节点左子树中的所有节点 比当前节点小
  • 节点右子树中的所有节点 比当前节点大

解题思路:

针对位于左子树的节点,判断它是否大于 leftMax;针对位于右子树的节点,判断它是否小于 rightMin;违反任一原则,都不是有效二叉搜索树。

思路说明图:

LeetCode 热题 100 | 二叉树(中下),力扣,leetcode,算法

当前节点(蓝色)作为分界线,一是作为其左子树(绿色)所有节点的上限,二是作为其右子树(黄色)所有节点的下限。当处理到 “6” 这节点时,它同样地,一是作为其左子树(“3”)所有节点的上限,二是作为其右子树(“8”)所有节点的下限。

对于节点 “3”,它的下限是 “5”,上限是 “6”;对于节点 “8”,它的下限是 “6”,没有上限。

class Solution {
public:
    bool helper(TreeNode* root, long long leftMax, long long rightMin) {
        if (!root) return true;

        if (root->val >= leftMax || root->val <= rightMin) return false;

        return helper(root->left, root->val, rightMin)
            && helper(root->right, leftMax, root->val);
    }

    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MAX, LONG_MIN);
    }
};

说明:什么是 LONG_MAX、LONG_MIN?

c++ 中最大值最小值的设定

3  230. 二叉搜索树中第 K 小的元素

解题思路:

  1. 遍历二叉树,将所有节点的数值存入一个数组中
  2. 使用 sort 对数组进行排序
  3. 返回 K - 1 号元素
class Solution {
public:
    vector<int> vals;

    void helper(TreeNode * root) {
        if (!root) return;

        vals.push_back(root->val);
        helper(root->left);
        helper(root->right);
    }

    int kthSmallest(TreeNode* root, int k) {
        helper(root);
        sort(vals.begin(), vals.end());
        return vals[k - 1];
    }
};

4  199. 二叉树的右视图

直接参照 102. 二叉树的层序遍历

解题思路:

  • 按 “层” 来遍历二叉树
  • 从右向左将同一层的节点的左右子节点插入到队列中
  • 在下一 “层” 循环中,队列将从右到左弹出下一 “层” 的所有节点
  • 将下一 “层” 的最右侧节点的值插入到数组中

思路说明:

首先将 “5” 插入到队列中。在 “5” 所处的 “层” 的循环中,弹出 “5”,依次将 “5” 的右子节点 “6” 和左子节点 “3” 插入到队列中。由于 “5” 是第一个弹出的节点,因此还要将其值插入到数组中。循环结束。接下来,在 “6” 所处的 “层” 的循环中,弹出 “6”,依次将 “6” 的右子节点和左子节点插入到队列中。由于 “6” 是第一个弹出的节点,因此还要将其值插入到数组中。再弹出 “3”,以此类推,……,直到循环结束。

LeetCode 热题 100 | 二叉树(中下),力扣,leetcode,算法

class Solution {
public:

    vector<int> rightSideView(TreeNode* root) {
        if (!root) return {};
        vector<int> vals;
        queue<TreeNode *> q;

        q.push(root);
        while (!q.empty()) {
            int currentLevelSize = q.size();
            for (int i = 0; i < currentLevelSize; ++i) {
                TreeNode * node = q.front();
                q.pop();
                if (i == 0) vals.push_back(node->val);
                if (node->right) q.push(node->right);
                if (node->left) q.push(node->left);
            }
        }
        return vals;
    }
};

说明:以下代码用于判断当前节点是否是最右侧节点文章来源地址https://www.toymoban.com/news/detail-831493.html

if (i == 0)

到了这里,关于LeetCode 热题 100 | 二叉树(中下)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • LeetCode 热题 100(七):105. 从前序与中序遍历序列构造二叉树、14. 二叉树展开为链表

    105. 从前序与中序遍历序列构造二叉树 https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ 思路:依据前序遍历的根左右和中序遍历的左根右, 且根左长度=左根 代码: 14. 二叉树展开为链表 https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/ 思路:前序遍历

    2024年02月10日
    浏览(47)
  • 【leetcode热题】对称二叉树

    难度: 简单 通过率: 42.2% 题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树  [1,2,2,3,4,4,3]  是对称的。 但是下面这个  [1,2,2,null,3,null,3]  则不是镜像对称的: 说明: 如果你可以运用递归和迭代两种方法

    2024年02月20日
    浏览(33)
  • 【leetcode热题】平衡二叉树

    难度: 简单 通过率: 39.9% 题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树 每个节点  的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 

    2024年02月21日
    浏览(37)
  • 二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”

    各位CSDN的uu们你们好呀,今天继续数据结构与算法专栏中的二叉树,下面,让我们进入二叉树的世界吧!!! 二叉树(上)——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客 二叉树链式结构的实现 二叉树链式结构的实现 求二叉树的高度 但是这种写法有很大的问题

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

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

    2024年02月14日
    浏览(40)
  • 【LeetCode 热题 100】矩阵 专题(大多原地算法,需要一定思维)

    解题思路 在 代码注释中!

    2024年02月15日
    浏览(47)
  • LeetCode热题HOT100:76. 最小覆盖子串,84.柱状图中最大的矩形、96. 不同的二叉搜索树

    题目 :给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串,我们保

    2023年04月19日
    浏览(56)
  • 二叉树OJ题:LeetCode--100.相同的树

    朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第100道二叉树OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏: 数据结构与算法 个  人  主  页  : stackY、 C 语 言 专 栏 : C语言:从入门到精通 LeetCo

    2024年02月11日
    浏览(33)
  • LeetCode(力扣)236. 二叉树的最近公共祖先Python

    https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

    2024年02月10日
    浏览(35)
  • 【leetcode100-042/043】【二叉树】二叉搜索树的转换和验证

    【转换】 给你一个整数数组  nums  ,其中元素已经按  升序  排列,请你将其转换为一棵  高度平衡  二叉搜索树。 高度平衡  二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 思路: 可以说是递归板子题了。每次把数组切两半,中间

    2024年01月20日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包