草庐IT

Leetcode.993 二叉树的堂兄弟节点

感觉画质不如…原神 2023-05-02 原文

题目链接

Leetcode.993 二叉树的堂兄弟节点 Rating ： 1288

题目描述

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x和 y。

只有与值 x和 y对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。

示例 1：

输入：root = [1,2,3,4], x = 4, y = 3
输出：false

示例 2：

输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true

示例 3：

输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false

提示：

  • 二叉树的节点数介于 2 到 100 之间。
  • 每个节点的值都是唯一的、范围为 1 到 100 的整数。

解法：bfs

使用 bfs ，每次访问处于 同一深度 的结点。

用 x f xf xf 表示结点 x x x 的父结点，用 y f yf yf 表示结点 y y y 的父结点。

如果 x f ≠ n u l l p t r & & y f ≠ n u l l p t r xf \neq nullptr \&\& yf \neq nullptr xf=nullptr&&yf=nullptr，说明结点 x x x 和 y y y 深度相同。如果 x f ≠ y f xf \neq yf xf=yf，说明结点 x x x 和 y y y 的父结点也不相同，故 结点 x x x 和 y y y 是堂兄弟结点，返回 true。

其他情况都返回 false。

时间复杂度： O ( n ) O(n) O(n)

C++代码：

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        queue<TreeNode*> q;
        q.push(root);

        TreeNode *xf = nullptr , *yf = nullptr;
        while(!q.empty()){
            int sz = q.size();

            for(int i = 0;i < sz;i++){
                auto t = q.front();
                q.pop();

                if(t->left){
                    q.push(t->left);
                    if(t->left->val == x) xf = t;
                    if(t->left->val == y) yf = t;
                }

                if(t->right){
                    q.push(t->right);
                    if(t->right->val == x) xf = t;
                    if(t->right->val == y) yf = t;
                }
            }
            //在同一层 并且 父结点不同 是堂兄弟结点
            if(xf && yf && (xf != yf)) return true;
            //不在同一层 不是堂兄弟结点
            if(xf || yf) return false;
        }

        return true;
    }
};
堂兄弟堂兄spanclasstoken算法leetcodec++

有关Leetcode.993 二叉树的堂兄弟节点的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. ruby - 在 Ruby 中实现二叉树 - 2

    我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:

  3. 区块链入门教程(6)--WeBASE-Front节点前置服务安装 - 2

    文章目录1.任务背景2.任务目标3.相关知识点4.任务实操4.1安装配置JDK4.2启动FISCOBCOS4.3下载解压WeBASE-Front4.4拷贝sdk证书文件4.5启动节点4.6访问节点4.7检查运行状态5.任务总结1.任务背景FISCOBCOS其实是有控制台管理工具，用来对区块链系统进行各种管理操作。但是对于初学者来说，还是可视化界面更友好，本节就来介绍WeBASE管理平台，这是一款微众银行开源的自研区块链中间件平台，可以降低区块链使用的门槛，大幅提高区块链应用的开发效率。微众银行是腾讯牵头设立的民营银行，在国内民营银行里还是比较出名的。微众银行参与FISCOBCOS生态建设，一定

  4. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  5. ruby - 选择包含子节点内文本的父节点 - 2

    基本上我想选择一个节点(div)，其中它的子节点(h1,b,h3)包含指定的文本。Childtext1Childtext2...Childtext3我期待的是/html/div/而不是/html/div/h1我在下面有这个，但不幸的是返回了child，而不是div的xpath。expression="//div[contains(text(),'Childtext1')]"doc.xpath(expression)我期待的是/html/div/而不是/html/div/h1那么有没有一种方法可以简单地使用xpath语法来做到这一点？ 最佳答案

  6. ruby - 删除指定节点之后的所有节点 - 2

    这个问题在这里已经有了答案:Nokogiri:SelectcontentbetweenelementAandB(3个答案)关闭2年前。我正在从url中抓取文本的div，并想删除具有backtotop类的段落下方的所有内容。我在stackoverflow上看到了一段遍历代码片段，看起来很有希望，但我不知道如何将它合并，所以@el只包含第一个p.backtotop之前的所有内容分区我的代码:@doc=Nokogiri::HTML(open(url))@el=@doc.css("div")[0]end遍历片段:doc=Nokogiri::HTML(code)stop_node=doc.css

  7. ruby - 如何从 Chef 说明书中的库访问当前节点？ - 2

    我正在尝试为ChefRecipe编写一个库，以简化一些常见的搜索。例如，我希望能够在cookbook/libraries/library.rb中执行类似的操作，然后从同一Recipe中的Recipe中使用它:moduleExampledefself.search_attribute(attribute_name)returnsearch(:nodes,node[attribute_name])endend问题是，在Chef库文件中，node对象或search函数都不可用。似乎可以使用Chef::Search::Query.new().search(...)进行搜索，但我找不到任何可以访

  8. ruby - 如何使用Nokogiri和XPath获取具有多个属性的节点 - 2

    我正在尝试使用Nokogiri来解析带有一些相当古怪的标记的HTML文件。具体来说，我正在尝试获取同时定义了id、多个类和样式的div。标记看起来像这样:titleListofstuff我正在尝试获取里面的问题.我可以毫无问题地获得具有单个id属性的div，但我想不出一种方法让Nokogiri获取具有和两个id类的div。所以这些工作正常:content=@doc.xpath("//div[id='foo']")content=@doc.css('div#foo')但是这些不返回任何东西:content=@doc.xpath("//div[id='bar']")content=@doc

  9. linux查看es节点使用情况,elasticsearch（es） 如何查看当前集群中哪个节点是主节点（master） - 2

    elasticsearch查看当前集群中的master节点是哪个需要使用_cat监控命令，具体如下。查看方法es主节点确定命令，以kibana上查看示例如下：GET_cat/nodesv返回结果示例如下：ipheap.percentram.percentcpuload_1mload_5mload_15mnode.rolemastername172.16.16.188529952.591.701.45mdi-elastic3172.16.16.187329950.990.991.19mdi-elastic2172.16.16.231699940.871.001.03mdi-elastic4172

  10. kubernetes集群划分节点 - 2

    Kubernetes（K8s）是一个用于管理容器化应用程序的开源平台，可以帮助开发人员更轻松地部署、管理和扩展应用程序。在Kubernetes中，集群划分是一种重要的概念，可以帮助我们更好地组织和管理集群中的节点和资源。本文将介绍如何使用Kubernetes对集群进行划分，并提供详细的操作示例，希望能够帮助读者更好地了解和使用Kubernetes平台。Node划分Node划分是将集群中的节点按照一定的规则进行划分。在Kubernetes中，可以使用NodeSelector和Affinity机制来实现Node划分。NodeSelectorNodeSelector是一种将Pod调度到符合特定节点标

随机推荐