Is there a DP solution for this problem?


  • 0

    My solution is quite easy, check each node with recursion:

    public class Solution {
        int ret = 0;
        public int countUnivalSubtrees(TreeNode root) {
            helper(root);
            return ret;
        }
        private void helper(TreeNode root){
            if(root==null) return;
            if(isUni(root)) ret++;
            helper(root.left);
            helper(root.right);
        }
        private boolean isUni(TreeNode root){
            if(root==null || (root.left==null && root.right==null)) return true;
            if(root.left!=null && root.val!=root.left.val) return false;
            if(root.right!=null && root.val!=root.right.val) return false;
            return (isUni(root.left) && isUni(root.right));
        }
    }
    

    While, this will involve duplicate check for some medium nodes. Is there is DP solution to avoid such duplicates?

    Thanks.


  • 0
    R

    You can use the bottom-up recursion to avoid duplicate check.


  • 0
    I

    i think your solution is O(n^2) right?


  • 0
    Y
    This post is deleted!

Log in to reply
 

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