基礎掃盲：二叉樹系列 第三講（二叉樹的剪枝）

• 2020 年 2 月 24 日
• 筆記

作者：程式設計師浩哥

在之前的系列中。我們學習了DFS、BFS，也熟悉了平衡二叉樹，滿二叉樹，完全二叉樹，BST（二叉搜索樹）等概念。在本節中，我們將學習一種二叉樹中常用的操作 — 剪枝。這裡額外說一點，就本人而言，對這個操作以及其衍化形式的使用會比較頻繁。因為我是做規則引擎的，在規則引擎中，我們會有一個概念叫做決策樹，那如果一顆決策樹完全生長，就會帶來比較大的過擬合問題。因為完全生長的決策樹，每個節點只會包含一個樣本。所以我們就需要對決策樹進行剪枝操作，來提升整個決策模型的泛化能力（ML概念）… 聽不懂也沒關係，簡單點講，就是我覺得這個很重要，或者每道演算法題都很重要。如果你在工作中沒有用到，不是說明演算法不重要，而可能是你還不夠重要。

01

剪枝概述

假設有一棵樹，最上層的是root節點，而父節點會依賴子節點。如果現在有一些節點已經標記為無效，我們要刪除這些無效節點。如果無效節點的依賴的節點還有效，那麼不應該刪除，如果無效節點和它的子節點都無效，則可以刪除。剪掉這些節點的過程，稱為剪枝，目的是用來處理二叉樹模型中的依賴問題。

我們通過題目來進行具體學習：

02

第814題：二叉樹的剪枝

第814題：給定二叉樹根結點 root ，此外樹的每個結點的值要麼是 0，要麼是 1。返回移除了所有不包含 1 的子樹的原二叉樹。

( 節點 X 的子樹為 X 本身，以及所有 X 的後代。)

示例1:

輸入: [1,null,0,0,1]

輸出: [1,null,0,null,1]

解釋:

只有紅色節點滿足條件「所有不包含 1 的子樹」。

右圖為返回的答案。

示例2:

輸入: [1,0,1,0,0,0,1]

輸出: [1,null,1,null,1]

示例3:

輸入: [1,1,0,1,1,0,1,0]

輸出: [1,1,0,1,1,null,1]

說明:

給定的二叉樹最多有 100 個節點。

每個節點的值只會為 0 或 1 。

03

遞歸求解

二叉樹的問題，大多都可以通過遞歸進行求解。我們直接進行分析。假設我們有二叉樹如下：[0,1,0,1,0,0,0,0,1,1,0,1,0]

長這樣：

剪枝之後是這樣：

剪什麼大家應該都能理解。那關鍵是怎麼剪？過程也很簡單，在遞歸的過程中，如果當前結點的左右節點皆為空，且當前結點為0，我們就將當前節點剪掉即可。

根據分析，很自然得出程式碼：

func pruneTree(root *TreeNode) *TreeNode {      return deal(root)  }    func deal(node *TreeNode) *TreeNode {      if node == nil {          return nil      }      node.Left = deal(node.Left)      node.Right = deal(node.Right)      if node.Left == nil && node.Right == nil && node.Val == 0 {          return nil      }      return node  }