從LeetCode學演算法 - 106 Tree (19) / DFS (16)

0563. Binary Tree Tilt (Easy)

寫在前面

抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/leetcodeadv

「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/leetcodeall

Question

Given the root of a binary tree, return the sum of every tree node’s *tilt *.

The tilt of a tree node is the ** absolute difference** between the sum of all left subtree node ** values** and all right subtree node ** values**. If a node does not have a left child, then the sum of the left subtree node ** values** is treated as 0. The rule is similar if there the node does not have a right child.

Example 1

1
2
3
4
5
6
7
Input: root = [1,2,3]
Output: 1
Explanation:
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tile of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
Input: root = [4,2,9,3,5,null,7]
Output: 15
Explanation:
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 5 : |0-0| = 0 (no children)
Tilt of node 7 : |0-0| = 0 (no children)
Tilt of node 2 : |3-5| = 2 (left subtree is just left child, so sum is 3; right subtree is just right child, so sum is 5)
Tilt of node 9 : |0-7| = 7 (no left child, so sum is 0; right subtree is just right child, so sum is 7)
Tilt of node 4 : |(3+5+2)-(9+7)| = |10-16| = 6 (left subtree values are 3, 5, and 2, which sums to 10; right subtree values are 9 and 7, which sums to 16)
Sum of every tilt : 0 + 0 + 0 + 2 + 7 + 6 = 15

Example 3

1
2
Input: root = [21,7,14,1,1,2,2,3,3]
Output: 9

Constraints

The number of nodes in the tree is in the range [0, 104].
-1000 <= Node.val <= 1000

分析/解題

給定一個二元樹，試計算二元樹的每個節點的tilt(坡度)和。

什麼是tilt呢?
題目告訴我們，對於一個節點，
其左子樹的和以及右子樹的和相減的絕對值，
就稱為它的坡度(tilt)，當子樹不存在時，和則視為0。

另外由於整個樹的總節點數已經被限定在0~104之間了，
表示我們可以放心的用遞迴！

那麼，我們該怎麼對每個節點算坡度呢？
對於一個節點n，如果它不存在的話(NIL)，
其坡度自然為0，且總和同樣為0 ；
存在的話，我們必須先算出左子樹(n.left為根節點的子樹)和，
以及右子樹(n.right為根節點的子樹)和，將兩者相減取絕對值，
就是n的坡度。

因此，我們可以使用一個dfs的函式來同時處理算子樹和，
以及坡度的部分，整個dfs的概念應該會如下：

若n為NIL，回傳0
將n.left代入dfs中，取得n.left的子樹和l
將n.right代入dfs中，取得n.right子樹和r
將|l-r|加到物件變數的答案res中
回傳l+r+n.val

留意到我們使用dfs的回傳一直都是回傳以n為根節點的子樹和，
這個和我們要計算的坡度不同，所以必須要用一個res變數來儲存。

在寫出dfs函式後，我們只需要初始化res，
並且在主函式中呼叫dfs後，回傳res即可。

依此，寫成程式碼如下：

Java 對於Java而言abs在java.lang.Math函式庫中，

如果不是在LeetCode的編輯器的話，不要忘記自行import。

Python

Python的部分和Java大同小異，
這邊採用將dfs寫成一個子函式，別忘記要宣告以後才能夠使用呦！
此外，__init__並非一定要這樣使用，在class Solution中直接定義也沒問題。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(樹的深度)，最差則為O(N))

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/1desolve