โจทย์
กำหนด Binary Tree หา Tilt ของทั้งต้นไม้ = ผลรวม Tilt ของทุกโหนด
Tilt ของโหนด = |Sum(Left Subtree) - Sum(Right Subtree)| (Leaf Node Tilt = 0)
ตัวอย่าง
4
/ \
2 9
/ \ \
3 5 7
Tilt(3) = |0-0| = 0
Tilt(5) = |0-0| = 0
Tilt(7) = |0-0| = 0
Tilt(2) = |3-5| = 2
Tilt(9) = |0-7| = 7
Tilt(4) = |(3+5+2) - (9+7)| = |10-16| = 6
Total Tilt = 0+0+0+2+7+6 = 15
แนวคิด: Post-order DFS
Post-order: คำนวณ Sum ของ Subtree ก่อน แล้วค่อยคำนวณ Tilt ที่ Node ปัจจุบัน
โค้ด C++
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// Return: Sum of subtree, Update global tilt sum
int dfsSum(TreeNode* node, int& totalTilt) {
if (!node) return 0;
int leftSum = dfsSum(node->left, totalTilt);
int rightSum = dfsSum(node->right, totalTilt);
totalTilt += abs(leftSum - rightSum);
return leftSum + rightSum + node->val;
}
int findTilt(TreeNode* root) {
int totalTilt = 0;
dfsSum(root, totalTilt);
return totalTilt;
}
// Alternative: Pair Return (Sum, Tilt)
pair<int, int> dfs(TreeNode* node) {
if (!node) return {0, 0};
auto [lSum, lTilt] = dfs(node->left);
auto [rSum, rTilt] = dfs(node->right);
int tilt = abs(lSum - rSum);
return {lSum + rSum + node->val, lTilt + rTilt + tilt};
}
int findTilt2(TreeNode* root) {
return dfs(root).second;
}
TreeNode* createNode(int val) {
return new TreeNode(val);
}
int main() {
// 4
// / \
// 2 9
// / \ \
// 3 5 7
TreeNode* root = createNode(4);
root->left = createNode(2);
root->right = createNode(9);
root->left->left = createNode(3);
root->left->right = createNode(5);
root->right->right = createNode(7);
cout << "Tilt: " << findTilt(root) << endl; // 15
cout << "Tilt v2: " << findTilt2(root) << endl; // 15
// Test: Single node
TreeNode* single = createNode(1);
cout << "Single: " << findTilt(single) << endl; // 0
// Test: Skewed
TreeNode* skew = createNode(1);
skew->left = createNode(2);
skew->left->left = createNode(3);
cout << "Skewed: " << findTilt(skew) << endl; // 3
return 0;
}
Complexity
- Time: O(n) - Visit each node once
- Space: O(h) - Recursion stack
Iterative Post-order (Two Stacks)
int findTiltIterative(TreeNode* root) {
if (!root) return 0;
stack<TreeNode*> s1, s2;
s1.push(root);
unordered_map<TreeNode*, int> sumMap;
while (!s1.empty()) {
TreeNode* node = s1.top(); s1.pop();
s2.push(node);
if (node->left) s1.push(node->left);
if (node->right) s1.push(node->right);
}
int totalTilt = 0;
while (!s2.empty()) {
TreeNode* node = s2.top(); s2.pop();
int lSum = node->left ? sumMap[node->left] : 0;
int rSum = node->right ? sumMap[node->right] : 0;
totalTilt += abs(lSum - rSum);
sumMap[node] = lSum + rSum + node->val;
}
return totalTilt;
}
ผลลัพธ์
Tilt: 15 Tilt v2: 15 Single: 0 Skewed: 3
สรุป
Binary Tree Tilt = Post-order DFS คำนวณ Subtree Sum แล้วหา |Left-Right| สะสมรวม ทุกโหนด - LeetCode 563 (Binary Tree Tilt)
