美文网首页程序猿日记机器学习与数据挖掘
Leetcode Python超琐碎笔记: 965. Univa

Leetcode Python超琐碎笔记: 965. Univa

作者: simoncos | 来源:发表于2019-01-08 14:59 被阅读37次

    超琐碎 ≈ 完整记录 + 深入探究 + 任性吐槽

    问题地址,难度:Easy,标签: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.

    Example 1:

    Input: [1,1,1,1,1,null,1]
    Output: true

    Example 2:

    Input: [2,2,2,5,2]
    Output: false

    Note:

    1. The number of nodes in the given tree will be in the range [1, 100].
    2. Each node's value will be an integer in the range [0, 99].

    题意分析

    这道题需要了解二叉搜索树的定义,以及递归/循环的知识。解决的思路:第一种是递归的每一步只看一对父子的值是否相等,然后传递下去,如果每一对都等,肯定全等;第二种是递归只管把所有节点值取出来,最后看一下是不是全等;第三种是先获取root的值,再递归搜索root的子树看是不是所有节点都等于这个值。

    实现方法(及调优过程)

    以下前两种方法对应LeetCode上的Solution,第三种是上面没有的。

    方法1:60 ms

    方法1对应第一种思路,看起来挺容易,但做起来有点绕。

    isUnivalTree(root)的结果即是“root所代表的子树是否为全等”这个命题的真值。首先须确定root到底有没有左子树和右子树,如果没有,则真值为True;如果有,则root的值与左右两个子节点的值必须相等,且两个子节点所代表的子树也必须是全等的,两个条件同时满足时真值为True

    下面贴的代码是我参考了Solution以后改的,原来的代码非常简洁(几乎就是逻辑运算式),我只是把逻辑运算的顺序改得清楚了点。

    # 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 = (not root.left) or ((root.val == root.left.val) and self.isUnivalTree(root.left))
            right = (not root.right) or ((root.val == root.right.val) and self.isUnivalTree(root.right))
            return left and right
    
    • 时间复杂度:O(n) (n为树的节点数,最坏情况下每个节点都被遍历)
    • 空间复杂度:O(m) (递归本身的栈会占用一些资源,m为树的深度,影响栈的数量)
    方法2:36 ms

    方法2对应第二种思路,个人感觉不够优雅,因为遍历完树以后还没有得到最后的答案(真值)。但实现起来容易多了。这里我直接贴了LeetCode上的Solution代码,其组织形式值得理解:values放在isUnivalTree里,isUnivalTree内部再写一个用于递归的函数getValues,这样values的作用域刚好使得getValues少一个丑陋的参数。

    # 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
            """
            values = []
            
            def getValues(node):
                if node:
                    values.append(node.val)
                    getValues(node.left)
                    getValues(node.right)
            
            getValues(root)
            return len(set(values)) == 1
    
    • 时间复杂度:O(n) (n为树的节点数,最坏情况下每个节点都被遍历)
    • 空间复杂度:O(m) (递归本身的栈会占用一些资源,m为树的深度,影响栈的数量)
    方法3:70 ms

    方法3的实现从组织方式上参考了方法2,而递归输出了真值则更像方法1,代码里比较tricky的地方是如果当前节点为None时,会返回True(方法1里其实也有这样的逻辑)。

    # 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
            """
            root_val = root.val
            
            def hasUniValue(node):
                if node:
                    return node.val == root_val and hasUniValue(node.left) and hasUniValue(node.right)
                else:
                    return True
            
            return hasUniValue(root) 
    

    弄清上面的逻辑后,还可仿照方法1改写hasUniValue,省略if语句。

            def hasUniValue(node):
                    return not node or (node.val == root_val and hasUniValue(node.left) and hasUniValue(node.right))
    
    • 时间复杂度:O(n) (n为树的节点数,最坏情况下每个节点都被遍历)
    • 空间复杂度:O(m) (递归本身的栈会占用一些资源,m为树的深度,影响栈的数量)

    相关文章

      网友评论

        本文标题:Leetcode Python超琐碎笔记: 965. Univa

        本文链接:https://www.haomeiwen.com/subject/qfmerqtx.html