image.png

深度优先搜索

我们先进行一次深度优先搜索，获取这颗树中的所有节点的值。然后，就可以判断所有节点的值是不是都相等了。

  1. class Solution {
  2.     List<Integer> list;
  3.     public boolean isUnivalTree(TreeNode root) {
  4.         list = new ArrayList<>();
  5.         dfs(root);
  6.         for(int ele:list){
  7.             if(ele!=list.get(0)){
  8.                 return false;
  9.             }
  10.         }
  11.         return true;
  12.     }
  13.     public void dfs(TreeNode root){
  14.         if(root!=null){
  15.             list.add(root.val);
  16.             dfs(root.left);
  17.             dfs(root.right);
  18.         }
  19.     }
  20. }

递归

一颗树是单值的，当且仅当根节点的子节点所在的子树也是单值的，同时根节点的值与子节点的值相同。

我们可以使用递归实现这个判断的过程。left_correct 表示当前节点的左孩子是正确的，也就是说：左孩子所在的子树是单值的，并且当前节点的值等于左孩子的值。right_correct 对当前节点的右孩子表示同样的事情。递归处理之后，当根节点的这两种属性都为真的时候，我们就可以判定这颗二叉树是单值的。

  1. public boolean isUnivalTree(TreeNode root) {
  2.         boolean left_correct = (root.left==null)||(root.val==root.left.val)&&isUnivalTree(root.left);
  3.         boolean right_correct = (root.right==null)||(root.val==root.right.val)&&isUnivalTree(root.right);
  4.         return left_correct&&right_correct;
  5.     }