leetcode965(单值二叉树)–Java语言实现

求：

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

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

示例 1：

输入：[1,1,1,1,1,null,1]
输出：true
示例 2：

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

提示：

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

题目链接： https://leetcode-cn.com/problems/univalued-binary-tree/

解：

1、深度优先搜索（DFS）

非常常规的题目，直接递归判断就可以了。

时间复杂度：O(N)

空间复杂度：O(N)

public boolean isUnivalTree(TreeNode root) {
    return theSame(root,root.val);
}

private boolean theSame(TreeNode root,int val){
    if(root==null)  return true;
    return root.val == val && theSame(root.left,val) && theSame(root.right,val);
}

2、广度优先搜索（BFS）

使用一个队列存储，然后如果判断有值不相等返回false，否则返回true。具体代码不再给出。

时间复杂度：O(N)

空间复杂度：O(N)