How does Binary Tree Pruning work?

Binary Tree Pruning involves performing a tree traversal (typically postorder DFS) to remove subtrees that do not contain a node with the value 1.

What is the time complexity of Binary Tree Pruning?

The time complexity is O(n), where n is the number of nodes in the tree, since each node is visited once during the traversal.

How does state tracking help in Binary Tree Pruning?

State tracking ensures that only subtrees containing a 1 are retained. As you traverse the tree, you track whether each node or its subtree contains a 1, determining if it should be pruned.

What are the common pitfalls in solving Binary Tree Pruning?

Common pitfalls include not performing a postorder DFS, failing to correctly track state, or using additional data structures that increase space complexity unnecessarily.

How does GhostInterview assist with Binary Tree Pruning?

GhostInterview provides step-by-step guidance, ensures correct traversal and pruning implementation, and offers feedback on optimizing both space and time complexity for Binary Tree Pruning.

#814

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

二叉树剪枝

给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。返回移除了所有不包含 1 的子树的原二叉树。节点 node 的子树为 node 本身加上所有 node 的后代。示例 1：输入： root = [1,null,0,0,1] 输出： [1,null,0,null,…

树深度优先搜索二叉树

题目描述

给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。

返回移除了所有不包含 1 的子树的原二叉树。

节点 node 的子树为 node 本身加上所有 node 的后代。

示例 1：

输入：root = [1,null,0,0,1]
输出：[1,null,0,null,1]
解释：
只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。

示例 2：

输入：root = [1,0,1,0,0,0,1]
输出：[1,null,1,null,1]

示例 3：

输入：root = [1,1,0,1,1,0,1,0]
输出：[1,1,0,1,1,null,1]

提示：

树中节点的数目在范围 [1, 200] 内
Node.val 为 0 或 1

lightbulb

解题思路

方法一：递归

我们首先判断当前节点是否为空，如果为空则直接返回空节点。

否则，我们递归地对左右子树进行剪枝，并将剪枝后的左右子树重新赋值给当前节点的左右子节点。然后判断当前节点的值是否为 0 且左右子节点都为空，如果是则返回空节点，否则返回当前节点。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为二叉树的节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return root
        root.left = self.pruneTree(root.left)
        root.right = self.pruneTree(root.right)
        if root.val == 0 and root.left == root.right:
            return None
        return root

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate understanding of binary tree traversal techniques like DFS.
question_mark
The candidate should be able to describe efficient state tracking methods and how they apply to pruning.
question_mark
The candidate should mention in-place tree modification and the importance of space optimization.

warning

常见陷阱

外企场景

error
Failing to perform a postorder traversal, which may lead to incorrect pruning.
error
Not maintaining state information correctly, leading to the retention of unnecessary subtrees.
error
Creating additional data structures unnecessarily, which can increase the space complexity of the solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Pruning only specific subtrees based on different criteria (e.g., pruning if the sum of nodes in the subtree is less than a certain threshold).
arrow_right_alt
Handling larger trees with optimizations like iterative DFS to avoid stack overflow for deep trees.
arrow_right_alt
Adapting the solution for binary search trees (BST), where the tree structure may influence traversal strategies.

help

常见问题

外企场景

继续练习

#783 二叉搜索树节点最小距离 #863 二叉树中所有距离为 K 的结点 #865 具有所有最深节点的最小子树