LeetCode 965. Univalued Binary Tree

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

内容简介: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

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

查看所有标签

猜你喜欢:

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

信息论、推理与学习算法

信息论、推理与学习算法

麦凯 / 高等教育出版社 / 2006-7 / 59.00元

本书是英国剑桥大学卡文迪许实验室的著名学者David J.C.MacKay博士总结多年教学经验和科研成果,于2003年推出的一部力作。本书作者不仅透彻地论述了传统信息论的内容和最新编码算法,而且以高度的学科驾驭能力,匠心独具地在一个统一框架下讨论了贝叶斯数据建模、蒙特卡罗方法、聚类算法、神经网络等属于机器学习和推理领域的主题,从而很好地将诸多学科的技术内涵融会贯通。本书注重理论与实际的结合,内容组......一起来看看 《信息论、推理与学习算法》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具