問題連結: https://leetcode.com/problems/binary-tree-pruning/
我們一開始的input是一個二元樹的根節點 root , 這個二元樹裡面的節點值非0即1
求回傳 "經過修剪過的同棵樹", 也就是希望把沒用的節點都移除, 這邊定義沒用的節點就是 只要這個節點為首的二元樹自己或自己的子節點們都沒有1, 整個節點都需要被移除
範例:
Input: [1,null,0,0,1]
Output: [1,null,0,null,1]
(如下圖)
解釋: 因為只有橘色節點所自己形成的小樹沒有包含任何1節點, 因此被移除了
想法:
其實這題沒有太難, 但我只是想要分享我如何想出如何解這題的過程
基本上我們就是要找到所有冗員節點並且把它們都裁掉, 當某節點自己還有他的所有子節點們全部都是冗員的時候, 他就被視為冗員
當我們從最一開始的根節點往下走的時候, 其實很難在碰到這個節點的時候, 就馬上知道他是不是冗員, 我們只能知道這個節點若自己的值非1, 那它"可能"是冗員 — 我們必須要真的走訪這個節點的所有子節點的時候, 我們才能真的確定它是否為冗員
因此, 最好從底往上走, 只要我們找到冗員節點, 代表它的父節點也危險了, 因為若父節點自己本身也冗, 然後他的另一個子節點也冗, 代表父節點也需要被移除了; 反之亦然, 若找到一個有用的節點, 代表它的父節點直接拿到免死金牌, 不管它自己本身的值或者它另一個子節點是否爭氣, 其實這些就像蝴蝶效應, 一個節點的結果 將會影響其上層所有節點
➡️因此, 解這題最簡單的方法就是用遞迴, 這樣我們就可以先檢查現在節點的子節點們, 才決定現在節點的狀態
程式邏輯:
既然我們已決定我們要做遞迴, 那我們先來想我們的base case為何(也就是什麼時候可以不用做事):
- 當現在傳入的節點為空, 那我們就回傳空, 因為也沒什麼好檢查的了
- 當傳入的節點為葉節點leaf node, 那我們判斷現在節點是否需要被移除的唯一條件就是看這個節點自己本身的值了, 若節點本身自己為0, 因為它也沒有子節點可以救它, 我們直接回傳空, 忽視這個節點的存在
好, 決定完base cases後, 我們來想想我們要怎麼檢查現在的節點是否需要被移除 —
在決定現在節點是否需要被移除前, 我們需要先確定 它的子節點是否需要被移除
而在檢查完兩個子節點的狀態後, (若子節點還有子節點, 那也會都檢查完它們後才能回報子節點的狀態), 我們又要再檢查一次 子節點的新狀態是否會造成現在的節點變成沒有孩子的狀態, 若現在節點的兩個子節點都被裁掉, 那我們又要重複我們上面提到的第二點base case的動作了, 為了降低程式碼的重複性, 我們把我們剛決定好的第二點base case移到這裡, 也就是在修剪完子節點後才一次檢查現在節點的狀態
若確定現在的節點不需要被移除(因為他的子節點夠爭氣), 那我們就可以放心的回傳現在節點, 畢竟我們也檢查和修剪過他的子節點跟子孫節點了
以下為 0ms 的程式碼, 贏過 100% —
public TreeNode pruneTree(TreeNode root) {
if(root==null)
return null;
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
if(root.left==null && root.right==null)//if leaf node
return root.val==0?null:root;
return root;
}
