Java Iterative Solution(BFS)


  • 0
    E
    public class Solution {
        public int countUnivalSubtrees(TreeNode root) {
            if (root == null) return 0;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int res = 0;
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                int count = isUnival(cur);
                if (count > 0) {
                    res += count;
                } else {
                    if (cur.left != null) {
                        queue.offer(cur.left);
                    }
                    if (cur.right != null) {
                        queue.offer(cur.right);
                    } 
                }
            }
            return res;
        }
        
        private int isUnival(TreeNode root) {
            if (root == null) return 0;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int val = root.val;
            int res = 0;
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                if (cur.val == val) {
                    res++;
                } else {
                    return 0;
                }
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.