從LeetCode學演算法 - 116 Tree (21) / DFS (19)

0814. Binary Tree Pruning (Medium)

寫在前面

(基礎+進階+面試篇) 從 LeetCode 學演算法 + 面試成功指南**http://bit.ly/zeroclg

新書(第一本，不曉得會不會是最後一本XD)開始預購啦！
初學 Python 的第一本書 : 從基本語法到模組應用（iT邦幫忙鐵人賽系列書） https://www.tenlong.com.tw/products/9789864348503
這本書主要是針對初學Python的入門讀者，希望能夠提供一個得以從零開始上手，又不會太過冗長的入門學習書。有興趣的話請多多支持！

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

Question

Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

A subtree of a node node is node plus every node that is a descendant of node.

Example 1

1
2
3
4
5
Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation:
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

Example 2

1
2
Input: root = [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]

Example 3

1
2
Input: root = [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]

Constraints

The number of nodes in the tree is in the range [1, 200].
Node.val is either 0 or 1.

分析/解題

給定一個二元樹的root，將同一棵樹中未含任何1的子樹均去除掉並回傳。
(限制條件：樹的節點數目在1~200之間，且Node的值只會是0或1)

如果我們看到範例的話，大致上可以理解要被去掉的部分就是包括自己以及其底下的所有節點值均為0的子樹，這樣才能保證剩下的符合題目要求的條件。

因此，我們總體要做的就是檢查一棵樹的左子樹及右子樹狀況，
然後分別決定左子樹/右子樹是否要被去掉，最後將當棵樹的總體狀況往上回傳，因此，設計一個子函數helper如下：

傳入要檢查的節點n
如果n是空節點，則直接回傳0(因為這代表往下左右沒有其它節點了，也不用繼續檢查)
遞迴檢查左子樹(將n.left代入helper)，取得左子樹含1的節點數量為l
遞迴檢查右子樹(將n.right代入helper)，取得右子樹含1的節點數量為r
若l為0，表示無左子樹或左子樹均無節點值為1的節點，將n.left設為NIL
同理，若r為0，將n.right設為NIL
回傳l+r+n.val

在將root代入helper遞迴結束後，所有root的子樹應該都被清乾淨了，
除了root自己以外，所以我們要檢查helper得到的最後的值，
若為0的話，則最終我們應回傳NIL，否則應回傳root。

依此，寫成程式碼如下：

Java

Java的部分使用三元運算子來處理最後的c，
其實我們也可以將整個helper的函式使用True/False來處理，
這樣中間的計算就要改成or來檢查是否至少存在一個節點值為1的節點。

Python

Python的部分使用子函數來簡單處理，其它的部分邏輯一樣。

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

「時間/空間複雜度？」
(O(N)/O(N)，N為節點總數，總體的遞迴深度則和樹的高度一致。)

相似及延伸

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

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

想看看其他題目嗎？
歡迎從第零篇 找你想要的！

同時追蹤粉專以獲得更多新文章的通知：
跟著Desolve學程式

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