根到叶路径上的不足节点【LC1080】
给你二叉树的根节点 root 和一个整数 limit ，请你同时删除树中所有 不足节点 ，并返回最终二叉树的根节点。
假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为 不足节点 ，需要被删除。
叶子节点，就是没有子节点的节点。
虽然写的有点麻烦 但还是写出来了
递归+先序+根据返回值删除孩子
- 思路
递归，函数的返回值为通过节点node的每种可能的 “根-叶” 路径上值的总和的最大值。在父节点处获得孩子节点的路径最大值，如果小于limit，那么将该孩子节点删除。 - 实现
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { int limit; public TreeNode sufficientSubset(TreeNode root, int limit) { this.limit = limit; // 最后可能整棵树都会被删除，因此需要设置哑结点指向根节点（类似链表） TreeNode dummyNode = new TreeNode(0); dummyNode.left = root; dfs(dummyNode, 0); return dummyNode.left; } public int dfs(TreeNode node, int path){ // 非叶子节点，为了不影响结果，返回最小值 if (node == null) return Integer.MIN_VALUE; path += node.val; // 叶子节点，返回该路径和 if (node.left == null && node.right == null){ return path; } // 获得中间节点可能的路径和（左或者右） // 若左孩子节点或者右孩子节点为空，那么是无效路径，路径和为最小值，不会影响结果 int l = dfs(node.left, path); int r = dfs(node.right, path); // 删除不足节点 if (l < limit){ node.left = null; } if (r < limit){ node.right = null; } // 返回左右路径的较大值 供父亲节点判断是否需要删除 return Math.max(l, r); } }
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
递归+先序+根据剩余值将叶子节点
- 思路
- 如果叶子节点的路径和小于
limit，那么直接将该叶子节点删除，即置为null即可
- 如果一个非叶子节点的孩子都被删除了，那么表明该节点的所有路径总和均小于limit，因此也将其置为null
- 实现
为了利用函数自身，每遍历一个节点修改limit值，当limit大于0时，表明路径和不符合要求，删除叶子
class Solution { public TreeNode sufficientSubset(TreeNode root, int limit) { // 根 limit -= root.val; // 左右 if (root.left == root.right) // root 是叶子 // 如果 limit > 0 说明从根到叶子的路径和小于 limit，删除叶子，否则不删除 return limit > 0 ? null : root; if (root.left != null) root.left = sufficientSubset(root.left, limit); if (root.right != null) root.right = sufficientSubset(root.right, limit); // 如果儿子都被删除，就删 root，否则不删 root return root.left == null && root.right == null ? null : root; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/solutions/2278769/jian-ji-xie-fa-diao-yong-zi-shen-pythonj-64lf/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
