根到叶路径上的不足节点【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);}
  }
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}(n)$
    • 空间复杂度：$\mathcal{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，否则不删 rootreturn 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）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。