Clean Java and C#Solution - with Explanation and Visualization - No Extra Data Structure


  • 3

    Steps:

    • Update the same tree and each node is gonna be sum of all the nodes below it, including itself. UpdateTreeSumDFS(root).
      For example:
      0_1503209367839_tree.png
    • Now, if any edge is removed, the separated subtree will have the sum=total_sum - its_value.
      For example if we remove 28's left subtree, we will have two trees which have sums of: 28-7=21 and 7.
    • We keep the total sum which is the given root's value. (Root of the updated tree).
    • Then we perform a DFS and check node by node, if by removing an edge, sum of the remaining nodes (rootSum - root.right.val) equals to sum of separated subtree (root.right.val), we return true.

    Code:

    Java:

        public boolean checkEqualTree(TreeNode root)
        {
            UpdateTreeSumDFS(root);
            return CheckEqualDFS(root,root.val);
        }
        private void UpdateTreeSumDFS(TreeNode root)
        {
            if (root == null) return;
    
            UpdateTreeSumDFS(root.left);
            UpdateTreeSumDFS(root.right);
    
            if (root.left != null)
                root.val += root.left.val;
    
            if (root.right != null)
                root.val += root.right.val;
        }
        private boolean CheckEqualDFS(TreeNode root,int rootSum)
        {
            if (root == null) return false;
    
            if(root.left!=null)
            {
                if (rootSum - root.left.val == root.left.val)
                    return true;
            }
    
            if(root.right!=null)
            {
                if (rootSum - root.right.val == root.right.val)
                    return true;
            }
    
            return CheckEqualDFS(root.left,rootSum) || CheckEqualDFS(root.right,rootSum);
    
        }  
    

    C#:

        public bool CheckEqualTree(TreeNode root)
        {
            UpdateTreeSumDFS(root);
            return CheckEqualDFS(root,root.val);
        }
        private void UpdateTreeSumDFS(TreeNode root)
        {
            if (root == null) return;
    
            UpdateTreeSumDFS(root.left);
            UpdateTreeSumDFS(root.right);
    
            if (root.left != null)
                root.val += root.left.val;
    
            if (root.right != null)
                root.val += root.right.val;
        }
        private bool CheckEqualDFS(TreeNode root,int rootSum)
        {
            if (root == null) return false;
    
            if(root.left!=null)
            {
                if (rootSum - root.left.val == root.left.val)
                    return true;
            }
    
            if(root.right!=null)
            {
                if (rootSum - root.right.val == root.right.val)
                    return true;
            }
    
            return CheckEqualDFS(root.left,rootSum) || CheckEqualDFS(root.right,rootSum);
    
        }
    

  • 0

    You're still using space for the recursion, so not O(1) space.


  • 0

    @StefanPochmann You're right as usual! Updating the title.


  • 1
    P

    Python verison inspired by your visualization!

    class Solution(object):
        def checkEqualTree(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            def update(node):
            	if not node:
            		return 0
            	node.val += update(node.left) + update(node.right)
            	return node.val
    
            target = update(root) / 2.0
    
            def check(node):
            	if node:
            		if node.val == target:
            			return True
            		return check(node.left) or check(node.right)
            	return False
    
            return check(root.left) or check(root.right)
    

Log in to reply
 

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