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. }