原問題網址:563. Binary Tree Tilt
問題描述
給定一棵 Binary Tree 的 root
,return 每個 node 的 tilt 加總值。
一個 tree node 的 tilt 的定義為:「所有左子樹的 node 的 value 加總」跟「所有右子樹的 node 的 value 加總」的 absolute difference。
如果一個 node 沒有左子樹,則其「所有左子樹的 node 的 value 加總」視為 0,右子樹也是如此。
解題思路
- 運用 Postorder traversal 在計算 value 加總的過程順便把每個 node 的 tilt 值算出來。(每個 node 只會被拜訪一次)
- 宣告一個 global 變數
totalTilt
紀錄上述步驟的值。
以下為用 C 語言實作的程式碼:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int totalTilt = 0;
int sumBinaryTree(struct TreeNode* root) {
if (!root) {
return 0;
}
int left = sumBinaryTree(root->left);
int right = sumBinaryTree(root->right);
totalTilt += abs(left - right);
return root->val + left + right;
}
int abs(int x) {
return (x < 0) ? -x : x;
}
int findTilt(struct TreeNode* root){
if (!root) {
return 0;
}
totalTilt = 0;
sumBinaryTree(root);
return totalTilt;
}