截止到目前我已經寫了 600多道演算法題，其中部分已經整理成了pdf檔案，目前總共有1000多頁（并且還會不斷的增加），大家可以免費下載
下載鏈接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取碼：6666
這題是說如果二叉樹的任一節點的左子樹都是0，就把他的左子樹洗掉，同理如果右子樹都是0，也把他的右子樹給洗掉，
這題常規思路是從根節點開始統計他的左右子樹節點是否都是0，如果任一子樹的所有節點都是0，就把他給洗掉，否則不能洗掉，然后再統計不能洗掉節點的子節點……，那這樣的話作業量就非常大，并且還會出現大量重復計算，如下圖所示：
上面方式明顯是行不通的，我們可以這樣來思考一下，從上到下刪不行，那么從下到上呢，如果是葉子節點并且值為0，我們就把他給洗掉，否則不要洗掉，看下視頻，視頻鏈接
看到這里大家可能就明白了，這就是二叉樹的后續遍歷，我們來看下代碼
public TreeNode pruneTree(TreeNode root) {
if (root == null)
return null;
//這里要注意，當前節點可能不是葉子節點，但如果他的子節點
//都洗掉完了，它就變成了葉子節點，
//剪枝左子樹
root.left = pruneTree(root.left);
//剪枝右子樹
root.right = pruneTree(root.right);
//如果葉子節點的值是0，就把他給洗掉，回傳一個空的節點
if (root.left == null && root.right == null && root.val == 0)
return null;
//否則不要洗掉，直接回傳即可
return root;
}
時間復雜度：O(n)，n是二叉樹中節點的個數，
空間復雜度：O(h)，h是樹的高度，也是遞回的深度，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/300790.html
標籤：其他