Easy

题目描述

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

给定一个二叉树的根节点 root，如果它是单值二叉树，则返回 true；否则返回 false。

示例 1：

输入：root = [1,1,1,1,1,null,1]
输出：true

示例 2：

输入：root = [2,2,2,5,2]
输出：false

提示：

  • 树中节点数目在范围 [1, 100] 内
  • 0 <= Node.val < 100

解题思路

这道题要求判断二叉树是否为单值树，即所有节点的值都相同。

思路分析：

  1. 递归深度优先搜索（推荐）：从根节点开始，递归检查每个节点的值是否与根节点的值相同。如果当前节点为空则返回true（空树视为满足条件）；如果当前节点值与根节点值不同则返回false；否则递归检查左右子树。

  2. 层次遍历（BFS）：使用队列进行层次遍历，检查每个节点的值是否与根节点值相同。

  3. 中序/前序/后序遍历：任何遍历方式都可以，关键是要访问所有节点并比较值。

递归DFS是最直观的解法，代码简洁且易理解。我们只需要确保每个节点的值都等于根节点的值即可。

核心逻辑：

  • 空节点返回true
  • 当前节点值不等于目标值返回false
  • 递归检查左右子树

代码实现

class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        if (!root) return true;
        return dfs(root, root->val);
    }
    
private:
    bool dfs(TreeNode* node, int val) {
        if (!node) return true;
        if (node->val != val) return false;
        return dfs(node->left, val) && dfs(node->right, val);
    }
};

class Solution:
    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        def dfs(node, val):
            if not node:
                return True
            if node.val != val:
                return False
            return dfs(node.left, val) and dfs(node.right, val)
        
        return dfs(root, root.val)

public class Solution {
    public bool IsUnivalTree(TreeNode root) {
        if (root == null) return true;
        return Dfs(root, root.val);
    }
    
    private bool Dfs(TreeNode node, int val) {
        if (node == null) return true;
        if (node.val != val) return false;
        return Dfs(node.left, val) && Dfs(node.right, val);
    }
}

var isUnivalTree = function(root) {
    if (!root) return true;
    
    const dfs = (node, val) => {
        if (!node) return true;
        if (node.val !== val) return false;
        return dfs(node.left, val) && dfs(node.right, val);
    };
    
    return dfs(root, root.val);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)，其中 n 是树中节点的数量，需要访问每个节点一次
空间复杂度O(h)，其中 h 是树的高度，递归调用栈的深度

相关题目