說明：本文是根據(jù)自己在 LeetCode 中文網(wǎng)站上發(fā)布的題解寫成的踊兜，即自己轉(zhuǎn)載了自己的文章帖努。
原文地址：
https://leetcode-cn.com/problems/insufficient-nodes-in-root-to-leaf-paths/solution/hou-xu-bian-li-python-dai-ma-java-dai-ma-by-liweiw/

首先考慮結(jié)點如何刪除

首先我們考慮如何刪除結(jié)點的問題。已知一個二叉樹中的結(jié)點要被刪除屎媳，有兩種辦法：1雄驹、自己刪除自己；2去件、告訴父親結(jié)點，自己需要從二叉樹中被刪除扰路。

“自己刪除自己”讓我想到了“單鏈表刪除某個結(jié)點”，如果這個要被刪除的結(jié)點是末尾結(jié)點倔叼，那還麻煩了汗唱。不過第 2 種辦法“告訴父親結(jié)點，自己需要從二叉樹中被刪除”丈攒，就很簡單了哩罪，父親結(jié)點收到孩子結(jié)點這個信號以后授霸，只要把對孩子結(jié)點的引用切斷即可。

其次考慮使用哪一種遍歷方式

二叉樹的問題一定離不開遍歷际插，遍歷有 DFS 和 BFS碘耳，根據(jù)題目中的描述“考慮它所有 從根到葉的路徑”，就知道不能用 BFS 了框弛，那么 DFS 又有 3 種辛辨，分別如下：

1、先序遍歷

（1）先執(zhí)行當(dāng)前結(jié)點的邏輯瑟枫；
（2）如果有左結(jié)點斗搞，就遞歸執(zhí)行左結(jié)點的邏輯；
（3）如果有右結(jié)點慷妙，就遞歸執(zhí)行右結(jié)點的邏輯僻焚。

2、中序遍歷

（1）如果有左結(jié)點膝擂，就遞歸執(zhí)行左結(jié)點的邏輯虑啤；
（2）先執(zhí)行當(dāng)前結(jié)點的邏輯；
（3）如果有右結(jié)點架馋，就遞歸執(zhí)行右結(jié)點的邏輯狞山。

3、后序遍歷

（1）如果有左結(jié)點绩蜻，就遞歸執(zhí)行左結(jié)點的邏輯铣墨；
（2）如果有右結(jié)點，就遞歸執(zhí)行右結(jié)點的邏輯办绝；
（3）先執(zhí)行當(dāng)前結(jié)點的邏輯伊约。

再看看我們首先考慮的問題，“告訴父親結(jié)點孕蝉，自己是否需要從二叉樹中被刪除”屡律，那么首先兩個子結(jié)點（如果存在的話）要清楚自己是不是需要被刪除，明顯使用“后序遍歷”降淮。

因此超埋，刪除結(jié)點（也可以稱為“剪枝”）的過程是從下到上的。

最后編碼實現(xiàn)

進行后序遍歷的時候佳鳖，要告訴父親節(jié)點自己是否需要從二叉樹中刪除霍殴，返回一個布爾值就可以了。這里編碼要注意幾個細節(jié)：

1系吩、 使用 Python 編碼的朋友来庭，盡量少使用 not，否定的判斷出現(xiàn)太多穿挨，比較容易把自己繞暈月弛，我這一版代碼是改過幾次的肴盏，原先我的 __dfs 方法設(shè)置的返回值的意思是“是否保留”。后來我把返回值的含義改成“是否刪除”帽衙，就是為了讓邏輯中少一些 not菜皂；

2、當(dāng)一個結(jié)點不是葉子結(jié)點的時候厉萝，它是否被刪除恍飘，也要看它的孩子結(jié)點，只要孩子結(jié)點有一個被保留冀泻，父親結(jié)點就不能被刪常侣，換句話說，父親結(jié)點被刪除當(dāng)且僅當(dāng)它的兩個孩子結(jié)點均被刪除弹渔；

image.png

3胳施、返回值的含義設(shè)置成“是否刪除”的前提下，左右孩子的默認(rèn)策略是刪除肢专，因為當(dāng)只有一個孩子結(jié)點存在的時候舞肆，這個孩子結(jié)點的刪除與否直接決定了父親結(jié)點是否被刪除，邏輯運算符 and 把不存在的那一邊設(shè)置為 True 博杖，就符合這個邏輯椿胯，不妨看看真值表，把其中一列全部設(shè)置成 True 剃根，and 的結(jié)果就正好和另外一列是一樣的：

如果你把 __dfs 方法的返回值意義設(shè)置成 是否保留哩盲，你就得看 or 那一列，并且左右孩子的默認(rèn)策略就是保留狈醉。

下面的示例代碼：

1廉油、Python 代碼：__dfs 方法返回值的意義是“當(dāng)前結(jié)點是否被刪除”；

2苗傅、Java 代碼：__dfs 方法返回值的意義是“當(dāng)前結(jié)點是否被保留”抒线。

請讀者比較它們二者的差別。

Python 代碼：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:

    def __dfs(self, node, s, limit):
        """
        后序遍歷
        :param node: 當(dāng)前遍歷的結(jié)點
        :param s: 當(dāng)前累計的和
        :param limit: 題目中給出的 limit
        :return: 是否要刪除 node 這個結(jié)點渣慕，True 表示要刪除嘶炭，F(xiàn)alse 表示不刪除
        """
        # 先寫遞歸終止條件：如果小于 limit，根據(jù)題意逊桦，要刪除
        if node.left is None and node.right is None:
            return s + node.val < limit

        # 默認(rèn)為左右結(jié)點均剪枝眨猎，注意：初值不能設(shè)置成 False
        l_tree_deleted = True
        r_tree_deleted = True

        # 如果有左子樹，就先遞歸處理左子樹
        if node.left:
            l_tree_deleted = self.__dfs(node.left, s + node.val, limit)

        # 如果有右子樹强经，就先遞歸處理右子樹
        if node.right:
            r_tree_deleted = self.__dfs(node.right, s + node.val, limit)

        # 左右子樹是否刪除的結(jié)論得到了宵呛，由自己來執(zhí)行是否刪除它們
        if l_tree_deleted:
            node.left = None
        if r_tree_deleted:
            node.right = None

        # 只有左右子樹都被刪除了，自己才沒有必要保留
        return l_tree_deleted and r_tree_deleted

    def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
        root_deleted = self.__dfs(root, 0, limit)
        if root_deleted:
            return None
        return root

Java 代碼：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {

    /**
     * @param node
     * @param s
     * @param limit
     * @return 返回 node 結(jié)點是否被保留（注意：這個返回值的意義夕凝，直接影響整個邏輯宝穗。）
     */
    private Boolean dfs(TreeNode node, int s, int limit) {
        if (node.left == null && node.right == null) {
            return s + node.val >= limit;
        }

        // 注意：如果 dfs 的返回值的意義是這個結(jié)點是否被保留，它們的默認(rèn)值應(yīng)該設(shè)置為 false
        boolean ltree_saved = false;
        boolean rtree_saved = false;

        // 如果有左子樹码秉，就先遞歸處理左子樹
        if (node.left != null) {
            ltree_saved = dfs(node.left, s + node.val, limit);
        }

        // 如果有右子樹逮矛，就先遞歸處理右子樹
        if (node.right != null) {
            rtree_saved = dfs(node.right, s + node.val, limit);
        }

        // 左右子樹是否保留的結(jié)論得到了，由自己來執(zhí)行是否刪除它們
        if (!ltree_saved) {
            node.left = null;
        }

        if (!rtree_saved) {
            node.right = null;
        }

        // 左右子樹有一顆被保留转砖，自己就應(yīng)該被保留
        return ltree_saved || rtree_saved;
    }

    public TreeNode sufficientSubset(TreeNode root, int limit) {
        boolean root_saved = dfs(root, 0, limit);
        if (!root_saved) {
            return null;
        }
        return root;
    }
}

復(fù)雜度分析：

• 時間復(fù)雜度：须鼎， 為二叉樹結(jié)點的個數(shù)。

• 空間復(fù)雜度：府蔗。

以上晋控，歡迎指正。