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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <math.h>
4
5struct TreeNode {
6 int val;
7 struct TreeNode *left;
8 struct TreeNode *right;
9};
10
11int findTiltUtil(struct TreeNode* root, int* tiltSum) {
12 if (root == NULL) return 0;
13
14 int leftSum = findTiltUtil(root->left, tiltSum);
15 int rightSum = findTiltUtil(root->right, tiltSum);
16
17 *tiltSum += abs(leftSum - rightSum);
18
19 return root->val + leftSum + rightSum;
20}
21
22int findTilt(struct TreeNode* root) {
23 int tiltSum = 0;
24 findTiltUtil(root, &tiltSum);
25 return tiltSum;
26}The C solution uses a helper function findTiltUtil which computes the sum of subtree node values and the tilt. It takes a pointer to tiltSum which accumulates the total tilt as a side effect.
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).
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 calculate_subtree_sum(self, node):
9 if not node:
10 return 0
11 return node.val + self.calculate_subtree_sum(node.left) + self.calculate_subtree_sum(node.right)
12
13 def calculate_tilt(self, node):
14 if not node:
15 return 0
16 left_sum = self.calculate_subtree_sum(node.left)
17 right_sum = self.calculate_subtree_sum(node.right)
18 left_tilt = self.calculate_tilt(node.left)
19 right_tilt = self.calculate_tilt(node.right)
20 return abs(left_sum - right_sum) + left_tilt + right_tilt
21
22 def findTilt(self, root):
23 return self.calculate_tilt(root)This Python solution structures the process with a focus on the use of inner methods to distinctly handle sum and tilt calculations. The recursive flow integrates cleanly with Python's dynamic type system.