Question

Formatted question description: https://leetcode.ca/all/250.html

 250	Count Univalue Subtrees

 Given a binary tree, count the number of uni-value subtrees.

 A Uni-value subtree means all nodes of the subtree have the same value.

 For example:
 Given binary tree,

    5
   / \
  1   5
 / \   \
5   5   5

 return 4.
     3 leaf nodes
     1 subtree 5-5 of right

 @tag-tree

Algorithm

Check from bottom to top, using post-order traversal order, left and right roots, we still call the function recursively,

For the currently traversed node, if the function is called recursively on the left and right child nodes, and the return is true,

Then it means that the value of the current node and the value of the left and right subtrees are the same, then there is another tree, so the result is incremented by 1.

Code

Java

public class Count_Univalue_Subtrees {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */

    // A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T.

    public class Solution_optimize {

        int res = 0;

        public int countUnivalSubtrees(TreeNode root) {

            isUnival(root, -1);
            return res;
        }

        boolean isUnival(TreeNode root, int val) {
            if (root == null) {
                return true;
            }

            boolean left = isUnival(root.left, root.val); // return meaning left is, and left-val == root-val
            boolean right = isUnival(root.right, root.val);
            if (!left | !right) {
                return false;
            }

            ++res;

            return root.val == val;

        }
    }

    public class Solution {
        private int result = 0;

        public int countUnivalSubtrees(TreeNode root) {
            if (root == null) {
                return result;
            }

            // check selected sub-root and all its decendants
            if (isUnival(root, root.val)) {
                ++result;
            }

            countUnivalSubtrees(root.left);
            countUnivalSubtrees(root.right);

            return result;
        }

        boolean isUnival(TreeNode root, int val) {

            if (root == null) {
                return true;
            }

            return root.val == val && isUnival(root.left, val) && isUnival(root.right, val);
        }
    }
}

All Problems

All Solutions