The idea behind the post-order traversal approach is to calculate the tilt of a node when all its children have been processed. For each node, compute the sum of node values for the left and right subtrees separately, calculate the node's tilt as the absolute difference of these two sums, and then propagate these subtree sums up to the parent node.
Time Complexity: O(n) where n is the number of nodes, as we visit each node once. Space Complexity: O(h) where h is the height of the tree, due to the recursion stack.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def findTilt(self, root: TreeNode) -> int:
9 self.tilt_sum = 0
10
11 def sum_and_tilt(node: TreeNode) -> int:
12 if not node:
13 return 0
14 left = sum_and_tilt(node.left)
15 right = sum_and_tilt(node.right)
16 self.tilt_sum += abs(left - right)
17 return node.val + left + right
18
19 sum_and_tilt(root)
20 return self.tilt_sumThe Python solution involves a recursive closure sum_and_tilt which mutates the state of self.tilt_sum to capture the total tilt progressively during the recursion.
In this approach, we preprocess the subtree sums for each node iteratively or recursively. Then we use these sums to calculate the tilt for each node in a separate pass through the tree. This separation of concerns can offer cleaner logic and easier maintenance of code.
Time Complexity: O(n^2) because calculateSubtreeSum might be called multiple times. Space Complexity: O(h).
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val);
3 this.left = (left===undefined ? null : left);
4 this.right = (right===undefined ? null : right);
5}
6
7function calculateSubtreeSum(node) {
8 if (node === null) return 0;
9 return node.val + calculateSubtreeSum(node.left) + calculateSubtreeSum(node.right);
10}
11
12function calculateTilt(node) {
13 if (node === null) return 0;
14 let leftSum = calculateSubtreeSum(node.left);
15 let rightSum = calculateSubtreeSum(node.right);
16 let leftTilt = calculateTilt(node.left);
17 let rightTilt = calculateTilt(node.right);
18 return Math.abs(leftSum - rightSum) + leftTilt + rightTilt;
19}
20
21var findTilt = function(root) {
22 return calculateTilt(root);
23};This JavaScript solution shows a clear separation of duties through separate functions for subtree sum and tilt calculations. This modularity enhances readability while maintaining functional purity.