最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

当前速看:1080. 根到叶路径上的不足节点

来源:博客园


(资料图片)

题目描述

给了一个二叉树,给了不足节点的定义(所有经过该节点的从跟到叶子的路径和如果都小于limt)需要删除所有的不足节点,返回最终的根节点

f1 分治+dfs

基本分析

  1. 从树上删除一个点,怎么操作方便?父节点删除比自己删除自己方便
  2. 以上信息给了什么启示?dfs中给父节点返回自己可以删除的信息,父节点去删除自己
  3. 如果某个节点的左右子节点都是不足节点,可以推出什么?这个节点也是不足节点(不重新计算路径值)
  4. 路径和怎么进行累加?定义s是从上往下传下去时候的路径和,最开始是0,每往下走,就会累加cur.val
  5. 为什么是后序遍历?拿到左右子节点的删除信息后,才能决定父节点是不是删除。

代码

class Solution:    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:        def dfs(cur, s, k):            if not cur.left and not cur.right:                return s + cur.val < k                        del_l, del_r = True, True            if cur.left:                del_l = dfs(cur.left, s + cur.val, k)            if cur.right:                del_r = dfs(cur.right, s + cur.val, k)                        if del_l:                cur.left = None            if del_r:                cur.right = None                        return del_l and del_r                del_root = dfs(root, 0, limit)        if del_root:            return None        else:            return root

总结

  1. 怎么理解递归?将s值传递下去,再从底层的return结果判断父节点的情况。
  2. 为啥在dfs之前要把删除初值设置为True?如果没有某个子树,就没法通过dfs传参设置为True,最终没法返回真实的and的结果(True and True)

关键词: