0814. Binary Tree Pruning¶
题目信息¶
- 题号:
0814
- 难度:
Medium
- 主题:
二叉树、子树删除、节点值
- 原题:
- 重点:
删除所有完全不含值 1 的子树;父节点值为 0 时,只要其后代含 1 就必须保留
题目重述¶
给定一棵节点值只可能为 0 或 1 的二叉树。若某个节点作为根的整棵子树中没有任何值为 1 的节点,就要把该子树从原树中删除。
请完成所有这样的删除并返回结果树的根节点。根节点所在的整棵树若不含 1,结果可以为空树。判断是否删除的是整个子树是否包含 1,不能只根据子树根节点自身的值决定。
树中节点数在 [1, 200] 范围内,每个节点值为 0 或 1。
自建示例¶
保留值为零但后代含一的节点:
输入:root = [0,0,1,0,null,0,1]
输出:[0,null,1,null,1]
解释:左子树全部为 0,因此整体删除;右子节点值为 1,需要保留,但它的左侧零叶子不含 1,会被删除。
整棵树都不含一:
输入:root = [0]
输出:[]
解释:单节点树达到题目允许的最小规模,根节点所在子树没有任何值为 1 的节点,因此根节点也被删除,结果为空树。