LeetCode 965. Univalued Binary Tree

栏目: 数据库 · 发布时间: 4年前

内容简介:A binary tree isReturn如果二叉树每个节点都具有相同的值,那么该二叉树就是
LeetCode 965. Univalued Binary Tree 题解

题目描述

  • 英文:

A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

  • 中文:

如果二叉树每个节点都具有相同的值,那么该二叉树就是 单值 二叉树。

只有给定的树是单值二叉树时,才返回 true ;否则返回 false

提示:

[1, 100]
[0, 99]

示例

  • 示例 1:
     1
   /   \
  1     1
 / \     \
1   1     1
输入:[1,1,1,1,1,null,1]
输出:true
  • 示例 2:
     2
   /   \
  2     2
 / \ 
5   2
输入:[2,2,2,5,2]
输出:false

题解

  • 题解 1

非递归解法。用一个队列记录未检查的节点,然后依次检查每个节点,判断节点的值是否与根节点的值相等,如果是,则检查是否有左右子节点,如果有则将其加入到队列,以待后续检查。然后,判断下一个节点。否则,返回False。直到所有节点都被检查完,再返回True。

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
    def isUnivalTree(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        q = [root]
        flag = root.val	# 单值
        while len(q) > 0:
            node = q[0]
            if node.val != flag:	# 一旦有一个不相同即不是单值二叉树树
                return False
            if node.left:
                q.append(node.left)	# 左子节点加入队列,待检查
            if node.right:
                q.append(node.right)	# 右子节点加入队列,待检查
            del q[0]
        return True
  • 题解 2

递归解法。依次检查每个节点,判断节点是否为空,左子节点和父节点是否相同,右子节点和父节点是否相同,左子节点和右子节点是否相同。

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
    def isUnivalTree(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        left = (root.left is None) or (root.val == root.left.val and self.isUnivalTree(root.left))
        right = (root.right is None) or (root.val == root.right.val and self.isUnivalTree(root.right))
        return left and right

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

解密SEO

解密SEO

欧朝晖 / 电子工业出版社 / 2007-05-01 / 49.80元

《解密SEO:搜索引擎优化与网站成功战略》帮助读者建立搜索营销的概念,分析搜索营销中的几种形式的手段,并从认识搜索引擎的原理开始,导出搜索引擎优化的具体解释,向读者引入以搜索引擎优化为宗旨的网站建设的新观念和设计理念。对网站结构优化、单页优化、链接优化等技术进行了详细的解说和示范。读者还可以接触到网站养育的新概念,帮助读者网站发展成熟,达到网络营销的目标。对搜索引擎优化中观念上和技术上常犯的错误,......一起来看看 《解密SEO》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具