Recursive Java solution with explanation


  • 0

    We need at least travel the tree once. One possible solution is travel every substree and recursively detect whether it's Univalue tree, that requires travel the tree multiple times.

    So we use a function boolean isUnivalSubtrees(TreeNode root) to travel the root and its subtrees. Meanwhile, the return boolean value indicate that whether itself is an univalue tree. Use the return value, it's parent can detect it's an univalue tree without travel all subtrees.

    private int total;
    
    public int countUnivalSubtrees(TreeNode root) {
        // reset for multiple call
        total = 0;
        this.isUnivalSubtree(root);
        return total;
    }
    
    public boolean isUnivalSubtree(TreeNode root) {
        if (root == null) { return false; }
        boolean l = this.isUnivalSubtree(root.left);
        boolean r = this.isUnivalSubtree(root.right);
        if (isSame(root, root.left, l) && isSame(root, root.right, r)) {
            total++;
            return true;
        }
        return false;
    }
    
    private boolean isSame(TreeNode root, TreeNode child, boolean s) {
        return child == null || s && root.val == child.val;
    }

Log in to reply
 

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