share my concise recursion method with O(1) space complexity


  • 1
    W
    1. check the sum of entire tree, if it isn't a multiple of 2, return false;
    2. if the tree can be divided into two equal trees, then there must be a node other than root with which we can build a subtree and the sum of it would be half of the sum of the entire tree.
    class Solution {
        public boolean checkEqualTree(TreeNode root) {
            int sum = sum(root);
            if(sum % 2 != 0) return false;
            
            return checkEqualTree(sum / 2, root.left) || checkEqualTree(sum / 2, root.right);
        }
        
        private boolean checkEqualTree(int target, TreeNode root){
            if(root == null) return false;
            return target == sum(root) || 
                (target == sum(root.left) && root.left != null) || 
                (target == sum(root.right) && root.right != null) ||
                checkEqualTree(target, root.left) || checkEqualTree(target, root.right);
        }
        
        public int sum(TreeNode root){
            if(root == null) return 0;
            return root.val + sum(root.left) + sum(root.right);
        }
    }
    

  • 0
    S

    the best solution I've ever seen!!!!!!!


Log in to reply
 

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