如果二叉树每个节点都具有相同的值,那么该二叉树就是 单值 二叉树。
只有给定的树是单值二叉树时,才返回 true
;否则返回 false
。
示例 1:
![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/29/screen-
shot-2018-12-25-at-50104-pm.png)
**输入:** [1,1,1,1,1,null,1]
**输出:** true
示例 2:
![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/29/screen-
shot-2018-12-25-at-50050-pm.png)
**输入:** [2,2,2,5,2]
**输出:** false
提示:
- 给定树的节点数范围是
[1, 100]
。
- 每个节点的值都是整数,范围为
[0, 99]
。
方法一:深度优先搜索
思路与算法
一棵树的所有节点都有相同的值,当且仅当对于树上的每一条边的两个端点,它们都有相同的值(这样根据传递性,所有节点都有相同的值)。
因此,我们可以对树进行一次深度优先搜索。当搜索到节点 x 时,我们检查 x 与 x 的每一个子节点之间的边是否满足要求。例如对于左子节点而言,如果其存在并且值与 x 相同,那么我们继续向下搜索该左子节点;如果值与 x 不同,那么我们直接返回 False。
代码
[sol1-C++]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public: bool isUnivalTree(TreeNode* root) { if (!root) { return true; } if (root->left) { if (root->val != root->left->val || !isUnivalTree(root->left)) { return false; } } if (root->right) { if (root->val != root->right->val || !isUnivalTree(root->right)) { return false; } } return true; } };
|
[sol1-Java]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public boolean isUnivalTree(TreeNode root) { if (root == null) { return true; } if (root.left != null) { if (root.val != root.left.val || !isUnivalTree(root.left)) { return false; } } if (root.right != null) { if (root.val != root.right.val || !isUnivalTree(root.right)) { return false; } } return true; } }
|
[sol1-C#]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| public class Solution { public bool IsUnivalTree(TreeNode root) { if (root == null) { return true; } if (root.left != null) { if (root.val != root.left.val || !IsUnivalTree(root.left)) { return false; } } if (root.right != null) { if (root.val != root.right.val || !IsUnivalTree(root.right)) { return false; } } return true; } }
|
[sol1-Python3]1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 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
|
[sol1-C]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| bool isUnivalTree(struct TreeNode* root){ if (!root) { return true; } if (root->left) { if (root->val != root->left->val || !isUnivalTree(root->left)) { return false; } } if (root->right) { if (root->val != root->right->val || !isUnivalTree(root->right)) { return false; } } return true; }
|
[sol1-JavaScript]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| var isUnivalTree = function(root) { if (!root) { return true; } if (root.left) { if (root.val !== root.left.val || !isUnivalTree(root.left)) { return false; } } if (root.right) { if (root.val !== root.right.val || !isUnivalTree(root.right)) { return false; } } return true; };
|
[sol1-Golang]1 2 3 4
| 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)) }
|
复杂度分析