Convert a binary tree to a sum tree / check if it is a sum tree
Problem
(1) Convert: replace each node's value with the sum of all values in its left and right subtrees (the original values); leaves become 0. (2) Check: return true if every non-leaf node already equals the sum of all nodes in its two subtrees.
Example 1
Input: convert [10, -2, 6, 8, -4, 7, 5] Output: [20, 4, 12, 0, 0, 0, 0]
Example 2
Input: check [26, 10, 3, 4, 6, null, 3] Output: true
Also asked as: Convert Binary tree into Sum tree · Check if Binary tree is Sum tree or not
Test cases
Case 1
Input: [10,-2,6,8,-4,7,5] Expected: [20,4,12,0,0,0,0]
Case 2
Input: [1,2,3] Expected: [5,0,0]
Case 3
Input: [1] Expected: [0]
View solutionHide solution1 approach
1. Post-order: replace with children sum / verify equality
Time O(n)Space O(h)
Convert: return oldValue + newLeft + newRight, set node.val to newLeft + newRight. Check: a node is valid iff its value equals the sum of both subtrees (leaves count as valid).
function toSumTree(node) { if (!node) return 0; const old = node.val; node.val = toSumTree(node.left) + toSumTree(node.right); return node.val + old;}function isSumTree(node) { if (!node || (!node.left && !node.right)) return true; const treeSum = (n) => (n ? n.val + treeSum(n.left) + treeSum(n.right) : 0); return node.val === treeSum(node.left) + treeSum(node.right) && isSumTree(node.left) && isSumTree(node.right);}