Given the root of a binary tree, return true if you can partition the tree into two trees with equal sums of values after removing exactly one edge on the original tree.
Input: root = [1,2,10,null,null,2,20]
Output: false
Explanation: You cannot split the tree into two trees with equal sums after removing exactly one edge on the tree.
Constraints:
The number of nodes in the tree is in the range [1, 104].
-105 <= Node.val <= 105
Solutions
Solution 1
1 2 3 4 5 6 7 8 9101112131415161718192021
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defcheckEqualTree(self,root:TreeNode)->bool:defsum(root):ifrootisNone:return0l,r=sum(root.left),sum(root.right)seen.append(l+r+root.val)returnseen[-1]seen=[]s=sum(root)ifs%2==1:returnFalseseen.pop()returns//2inseen
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funccheckEqualTree(root*TreeNode)bool{varseen[]intvarsumfunc(root*TreeNode)intsum=func(root*TreeNode)int{ifroot==nil{return0}l,r:=sum(root.Left),sum(root.Right)s:=l+r+root.Valseen=append(seen,s)returns}s:=sum(root)ifs%2!=0{returnfalse}seen=seen[:len(seen)-1]for_,v:=rangeseen{ifv==s/2{returntrue}}returnfalse}