Java Tree Traversal O(n) Time O(n) Space


  • 0
    public boolean checkEqualTree(TreeNode root) {
        Map<TreeNode, Integer> map = new HashMap<>();
        return canPartition(root, map, getSubtreeSums(root, map));
    }
    
    public int getSubtreeSums(TreeNode root, Map<TreeNode, Integer> map) {
        if (root == null) return 0;
        map.put(root, root.val + getSubtreeSums(root.left, map) + getSubtreeSums(root.right, map));
        return map.get(root);
    }
    
    public boolean canPartition(TreeNode root, Map<TreeNode, Integer> map, int totalSum) {
        if (root == null) return false;
        return totalSum == 2*map.getOrDefault(root.left, -1) || totalSum == 2*map.getOrDefault(root.right, -1) ||
               canPartition(root.left, map, totalSum) || canPartition(root.right, map, totalSum);
    }
    

Log in to reply
 

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