814. 二叉樹剪枝 : 簡單遞歸運用題

題目描述

這是 LeetCode 上的 ​​814. 二叉樹剪枝​​ ，難度為 中等。

Tag : 「二叉樹」、「DFS」、「遞歸」

給你二叉樹的根結點 ​

​root​

​​，此外樹的每個結點的值要麼是 ，要麼是

傳回移除了所有不包含

節點 ​

​node​

​​ 的子樹為 ​

​node​

​​ 本身加上所有 ​

​node​

​ 的後代。

示例 1：

輸入：root = [1,null,0,0,1]

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

解釋：
隻有紅色節點滿足條件“所有不包含 1      

示例 2：

輸入：root = [1,0,1,0,0,0,1]

輸出：[1,null,1,null,1]      

示例 3：

輸入：root = [1,1,0,1,1,0,1,0]

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

提示：

• 樹中節點的數目在範圍
• ​

  ​Node.val​

  ​​ 為或

遞歸

根據題意，我們将原函數 ​

​pruneTree​

​​ 作為遞歸函數，遞歸函數的含義為「将入參 ​

​root​

​​ 中的所有不包含

不失一般性的考慮任意節點作為入參該如何處理：我們可以遞歸處理左右子樹，并将新左右子樹重新指派給 ​

​root​

​​。由于目前節點 ​

​root​

​ 的左右子樹可能為空樹，是以我們要增加遞歸函數入參為空的邊界處理。

當遞歸操作完成後，若左右節點任一值不為空（說明目前節點 ​

​root​

​​ 不為葉子節點），我們可以直接傳回 ​

​root​

​​，否則根據 ​

​root​

​​ 的值是否為 來決定傳回空樹還是 ​​

​root​

​ 本身。

Java 代碼：

class Solution {
    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) return root;
        return root.val == 0 ? null      

TypeScript 代碼：

function pruneTree(root: TreeNode | null): TreeNode | null {
    if (root == null) return null
    root.left = pruneTree(root.left)
    root.right = pruneTree(root.right)
    if (root.left != null || root.right != null) return root
    return root.val == 0 ? null      

• 時間複雜度：
• 空間複雜度：忽略遞歸帶來的額外空間開銷，複雜度為

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.814​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。