[100天算法】-二叉树剪枝（day 48）
题目描述
给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。返回移除了所有不包含 1 的子树的原二叉树。( 节点 X 的子树为 X 本身，以及所有 X 的后代。)示例1:
输入: [1,null,0,0,1]
输出: [1,null,0,null,1]示例2:
输入: [1,0,1,0,0,0,1]
输出: [1,null,1,null,1]示例3:
输入: [1,1,0,1,1,0,1,0]
输出: [1,1,0,1,1,null,1]说明:给定的二叉树最多有 100 个节点。
每个节点的值只会为 0 或 1 。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-pruning
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
用【产品经理法】的思维来解决递归问题。
产品
假设我们已经有了一个 pruneTree 方法，可以把一棵树中不包含 1 的枝节删掉。
子问题
明显是 pruneTree(root.left) 和 pruneTree(root.right)。
大小问题的关系
首先，对于 root，我们用 pruneTree(root.left) 和 pruneTree(root.right) 的结果分别替换掉原本的 root.left 和 root.right。接着，再决定当前这棵树要不要保留。
- 如果此时左右子树有一个不为空的话，那说明这棵树是要保留的，直接返回
root就行。 - 如果左右子树都为空，那我们就判断
root.val的值，等于 1 就返回root，等于 0 就返回null把这棵树移除。
递归出口
空节点直接返回 null 就行。
代码
TypeScript Code
/*** Definition for a binary tree node.* class TreeNode {* val: number* left: TreeNode | null* right: TreeNode | null* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {* this.val = (val===undefined ? 0 : val)* this.left = (left===undefined ? null : left)* this.right = (right===undefined ? null : right)* }* }*/function pruneTree(root: TreeNode | null): TreeNode | null {if (!root) return null;root.left = pruneTree(root.left);root.right = pruneTree(root.right);return root.left || root.right || root.val === 1 ? root : null;
}
复杂度分析
- 时间复杂度：$O(N)$，N 为二叉树节点数。
- 空间复杂度：$O(H)$，H 为二叉树的高度，递归栈的最大空间。