Java Solution, 2 recursions, No Hash Table


  • 0
    F
    class Solution {
        private static class RetVal {
            public int sum;
            public boolean canSplit;
            
            public RetVal(int s, boolean canS) {
                sum = s;
                canSplit = canS;
            }
        }
        
        public boolean checkEqualTree(TreeNode root) {
            if(root == null) {
                return false;
            } else {
                int sum = getSum(root);
                
                if(split(root.left, sum).canSplit || split(root.right, sum).canSplit) {
                    return true;
                } else {
                    return false;
                }
            }
        }
        
        private int getSum(TreeNode node) {
            if(node == null) {
                return 0;
            } else {
                return getSum(node.left)+getSum(node.right)+node.val;
            }
        }
        
        private RetVal split(TreeNode node, final int sum) {
            if(node == null) {
                return new RetVal(0, false);
            } else {
                RetVal lRet, rRet;
                
                if((lRet = split(node.left, sum)).canSplit || (rRet = split(node.right, sum)).canSplit) {
                    return new RetVal(0, true);
                } else {
                    return new RetVal(node.val+lRet.sum+rRet.sum, (node.val+lRet.sum+rRet.sum << 1) == sum);
                }
            }
        }
    }
    

Log in to reply
 

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