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 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8class Solution {
9 private int tiltSum = 0;
10
11 public int findTilt(TreeNode root) {
12 sumAndTilt(root);
13 return tiltSum;
14 }
15
16 private int sumAndTilt(TreeNode node) {
17 if (node == null) return 0;
18
19 int left = sumAndTilt(node.left);
20 int right = sumAndTilt(node.right);
21 tiltSum += Math.abs(left - right);
22 return node.val + left + right;
23 }
24}In the Java solution, a class-level variable tiltSum is used to store the total tilt. The sumAndTilt method calculates the subtree sums and tilt for a node.
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).
1#include <cmath>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13 int calculateSubtreeSum(TreeNode* node) {
14 if (node == nullptr) return 0;
15 return node->val + calculateSubtreeSum(node->left) + calculateSubtreeSum(node->right);
16 }
17
18 int calculateTilt(TreeNode* node) {
19 if (node == nullptr) return 0;
20 int leftSum = calculateSubtreeSum(node->left);
21 int rightSum = calculateSubtreeSum(node->right);
22 int leftTilt = calculateTilt(node->left);
23 int rightTilt = calculateTilt(node->right);
24 return abs(leftSum - rightSum) + leftTilt + rightTilt;
25 }
26
27 int findTilt(TreeNode* root) {
28 return calculateTilt(root);
29 }
30};In this C++ implementation, we separate the computation of subtree sums and the tilt using separate methods and a recursive approach. Calculating the sum and tilt in distinct passes allows for clear readability.