【树】B038_LC_根到叶路径上的不足节点（后序遍历）

一、Problem

给定一棵二叉树的根 root，请你考虑它所有 从根到叶的路径：从根到任何叶的路径。（所谓一个叶子节点，就是一个没有子节点的节点）

假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为「不足节点」，需要被删除。

请你删除所有不足节点，并返回生成的二叉树的根。

[1,2,-3,-5,null,4,null]
-1

提示：

给定的树有 1 到 5000 个节点
-10^5 <= node.val <= 10^5
-10^9 <= limit <= 10^9

二、Solution

方法一：后序遍历

思路

因为我们要判断以某一个结点 node 为根的左路径和右路径是否满足被删除的要求，所以后序遍历会是一个不错的选择

当遍历到叶子结点时，如果路径总和小于 limit 那么该叶子结点就要被删除，怎么删除呢？当然要将删除信息传递给它的父亲啦，所以我们的返回值选择 bool 类型

如果某一个父亲结点的左右孩子都被删除了，证明经过父亲这个结点可能的所有「根-叶」路径的总和小于 limit，所以这个父亲结点要被删除，反之这个父节点不需要被删除

class Solution {
    boolean dfs(TreeNode root, int s, int lim) {
        if (root == null)
            return true;
        s += root.val;
        if (root.left == null && root.right == null)
            return s < lim;
        boolean delLeft = dfs(root.left, s, lim);
        boolean delRight = dfs(root.right, s, lim);
        if (delLeft)  root.left = null;
        if (delRight) root.right = null;
        return delLeft && delRight;
    }
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        return dfs(root, 0, limit) ? null : root;
    }
}

复杂度分析

• 时间复杂度：$O(n)$O(n)，
• 空间复杂度：$O(1)$O(1)，