[LeetCode 解題筆記] Binary Tree Tilt

原問題網址：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;
}