『LeetCode』965 单值二叉树

题目

965. 单值二叉树

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

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

示例 1：

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

示例 2：

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

提示：

• 给定树的节点数范围是 [1, 100]。
• 每个节点的值都是整数，范围为 [0, 99] 。

---

题解

【单值二叉树】简单逻辑判断

递归

简单来说：

• 如果有左子树，根结点和左孩子结点值要相同，且左子树是单值二叉树
• 如果有右子树，根结点和右孩子结点值要相同，且右子树是单值二叉树

很简单的逻辑判断

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

// Code language: Java
class Solution {
    public boolean isUnivalTree(TreeNode root) {
        if (root != null) {
            if (root.left != null && (root.left.val != root.val || !isUnivalTree(root.left)))
                return false;
            if (root.right != null && (root.right.val != root.val || !isUnivalTree(root.right)))
                return false;
        }
        return true;
    }
}

// Code language: Cpp
class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        if (root != nullptr) {
            if (root->left != nullptr && (root->left->val != root->val || !isUnivalTree(root->left)))
                return false;
            if (root->right != nullptr && (root->right->val != root->val || !isUnivalTree(root->right)))
                return false;
        }
        return true;
    }
};

可以压缩到一行🤣🤣

# Code language: Python
class Solution:
    def isUnivalTree(self, root: TreeNode) -> bool:
        return not root or (not (root.left and (root.left.val != root.val or not self.isUnivalTree(root.left))) and not (root.right and (root.right.val != root.val or not self.isUnivalTree(root.right))))

// Code language: Java
class Solution {
    public boolean isUnivalTree(TreeNode root) {
        return root == null || (!(root.left != null && (root.left.val != root.val || !isUnivalTree(root.left))) && !(root.right != null && (root.right.val != root.val || !isUnivalTree(root.right))));
    }
}

// Code language: Cpp
class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        return root == nullptr || (!(root->left != nullptr && (root->left->val != root->val || !isUnivalTree(root->left))) && !(root->right != nullptr && (root->right->val != root->val || !isUnivalTree(root->right))));
    }
};

• 时间复杂度: \(O(n)\), \(n\) 表示二叉树结点数量
• 空间复杂度: \(O(1)\)，忽略递归开销

---

迭代

以任意常规或非常规的顺序遍历一遍二叉树即可判断

# Code language: Python
class Solution:
    def isUnivalTree(self, root: TreeNode) -> bool:
        st = [root]
        val = root.val
        while st:
            cur = st.pop()
            if not cur.val == val:
                return False
            if cur.left: st.append(cur.left)
            if cur.right: st.append(cur.right)
        return True

// Code language: Java
class Solution {
    public boolean isUnivalTree(TreeNode root) {
        Deque<TreeNode> st = new ArrayDeque<>();
        if (root == null) return true;
        st.addLast(root);
        int val = root.val;
        while (!st.isEmpty()) {
            TreeNode cur = st.pollLast();
            if (cur.val != val) return false;
            if (cur.left != null) st.addLast(cur.left);
            if (cur.right != null) st.addFirst(cur.right);
        }
        return true;
    }
}

// Code language: Cpp
class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        vector<TreeNode*> st;
        if (root == nullptr) return true;
        st.emplace_back(root);
        int val = root->val;
        while (!st.empty()) {
            TreeNode* cur = st.back();
            st.pop_back();
            if (cur->val != val) return false;
            if (cur->left != nullptr) st.emplace_back(cur->left);
            if (cur->right != nullptr) st.emplace_back(cur->right);
        }
        return true;
    }
};

• 时间复杂度: \(O(n)\), \(n\) 表示二叉树结点数量
• 空间复杂度: \(O(n)\)