Time O(N) Space O(1) Easy Solution without Global Variable (13 ms beats 95.8%)


  • 3
    L

    The idea is very simple. It is a two pass method.
    First pass is to get the total sum of whole tree.
    Second pass is almost the same as first time.
    The only difference is that each node needs to check if the total sum of its current subtree equals to sum/2.

    The time complexity is O(N) and the space complexity is O(1) not considering the memory occupation of recursion.

    public boolean checkEqualTree(TreeNode root) {
    	// check root
    	if(root == null) {
    		return false;
    	}
    	// get the total sum
    	int sum = getTotalSum(root);
    
    	// check  if the sum can be divided by 2
    	if(sum % 2 != 0) {
    		return false;
    	}
    	boolean[] isFind = new boolean[1];
    	checkSubtreeSum(root.left, sum / 2, isFind);
            // check if already find out from the left side
            if(isFind[0]) {
                return isFind[0];
            }
            checkSubtreeSum(root.right, sum / 2, isFind);
            return isFind[0];
    }
    
    
    private int getTotalSum(TreeNode node) {
    	if(node == null) {
    		return 0;
    	}
    	return node.val + getTotalSum(node.left) + getTotalSum(node.right);
    }
    
    private int checkSubtreeSum(TreeNode node, int target, boolean[] isFind) {
    	if(node == null || isFind[0]) {
    		return 0;
    	}
    	int curNum = node.val + checkSubtreeSum(node.left, target, isFind) + checkSubtreeSum(node.right, target, isFind);
    	if(curNum == target) {
    		isFind[0] = true;
    	}
    	return curNum;
    
    }
    

Log in to reply
 

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