深度优先搜索
我们先进行一次深度优先搜索,获取这颗树中的所有节点的值。然后,就可以判断所有节点的值是不是都相等了。
class Solution {
List<Integer> list;
public boolean isUnivalTree(TreeNode root) {
list = new ArrayList<>();
dfs(root);
for(int ele:list){
if(ele!=list.get(0)){
return false;
}
}
return true;
}
public void dfs(TreeNode root){
if(root!=null){
list.add(root.val);
dfs(root.left);
dfs(root.right);
}
}
}
递归
一颗树是单值的,当且仅当根节点的子节点所在的子树也是单值的,同时根节点的值与子节点的值相同。
我们可以使用递归实现这个判断的过程。left_correct 表示当前节点的左孩子是正确的,也就是说:左孩子所在的子树是单值的,并且当前节点的值等于左孩子的值。right_correct 对当前节点的右孩子表示同样的事情。递归处理之后,当根节点的这两种属性都为真的时候,我们就可以判定这颗二叉树是单值的。
public boolean isUnivalTree(TreeNode root) {
boolean left_correct = (root.left==null)||(root.val==root.left.val)&&isUnivalTree(root.left);
boolean right_correct = (root.right==null)||(root.val==root.right.val)&&isUnivalTree(root.right);
return left_correct&&right_correct;
}