【刷题】965. 单值二叉树

• 题目
• 思路
• 解题
• • python实现
  • golang实现
• 复杂度
• 总结

leetCode链接：https://leetcode.cn/problems/univalued-binary-tree/

965. 单值二叉树

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

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

下图为一个单值二叉树：

下图不是单值二叉树：

相当简单的DFS题目，以root值无脑DFS即可。

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

class Solution:
    def dfs(self,val,root):
        if root.val!=val:
            return False
        left_confirm = self.dfs(val,root.left) if root.left!=None else True
        right_confirm = self.dfs(val,root.right) if root.right!=None else True
        return left_confirm and right_confirm
        
    def isUnivalTree(self, root: TreeNode) -> bool:
        return self.dfs(root.val,root)

func isUnivalTree(root *TreeNode) bool {
    var dfs func(root *TreeNode,val int) bool
    dfs = func(root *TreeNode,val int) bool {
        if root.Val!=val{
            return false
        }
        return (root.Left==nil || dfs(root.Left,root.Val))&&(root.Right==nil || dfs(root.Right,root.Val))
    }
    return dfs(root,root.Val)
}

时间复杂度： O ( n ) Omicron(n) O(n),其中 n 是二叉树的节点个数。每个节点至多遍历一次。

空间复杂度： O ( n ) O(n) O(n)，深度优先搜索中需要使用的栈空间。

看了答案写的十分优雅。。相比之下有点无地自容。。
还需要不断锻练内功啊

python:

class Solution:
    def isUnivalTree(self, root: TreeNode) -> bool:
        if not root:
            return True
        
        if root.left:
            if root.val != root.left.val or not self.isUnivalTree(root.left):
                return False
        
        if root.right:
            if root.val != root.right.val or not self.isUnivalTree(root.right):
                return False
        
        return True

golang:

func isUnivalTree(root *TreeNode) bool {
    return root == nil || (root.Left == nil || root.Val == root.Left.Val && isUnivalTree(root.Left)) &&(root.Right == nil || root.Val == root.Right.Val && isUnivalTree(root.Right))
}