0814. Binary Tree Pruning

题目信息

题号:

0814

难度:

Medium

主题:

二叉树、子树删除、节点值

原题:

LeetCode 0814

重点:

删除所有完全不含值 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 的节点,因此根节点也被删除,结果为空树。