814.二叉树剪枝

【LetMeFly】814.二叉树剪枝

力扣题目链接：https://leetcode.cn/problems/binary-tree-pruning/

给你二叉树的根结点 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

方法一：DFS

递归，返回结果的同时进行修剪。

因为涉及到一个节点的所有子树，因此很适合深搜DFS。

构建一个函数isZero，用来判断一个节点是否是某个全0子树的根。同时，如果这个节点的左子树是全0子树，就剪掉这个节点的左子树；右子树同理。

/* 判断此节点的 左/右 子树是否为全0二叉树。若是，则移除对应子树 */
bool isZero(TreeNode* root) {
	bool is0 = true;  // 这个节点是否为全0子树的根
	if (root->val)  // 如果这个节点的值为1
		is0 = false;  // 直接排除全0子树
	// 判断左子树是否为全0子树。如果是，就修剪之
	if (root->left) {  // 前提是左子树不空
		if (isZero(root->left)) {  // 左子树是全0子树
			root->left = nullptr;  // 左子树设置为空（这样就修剪掉了）
		}
		else {  // 左子树不是全0子树
			is0 = false;  // 那么“父树”更不是全0树
		}
	}
	// 右子树同理
	if (root->right) {
		if (isZero(root->right)) {
			root->right = nullptr;
		}
		else {
			is0 = false;
		}
	}
	return is0;
}

• 时间复杂度$O(N)$，其中$N$是节点的个数
• 空间复杂度$O(N)$，空间复杂度主要来自递归

AC代码

C++

class Solution {
private:
    /* 判断此节点的 左/右 子树是否为全0二叉树。若是，则移除对应子树 */
    bool isZero(TreeNode* root) {
        bool is0 = true;
        if (root->val)
            is0 = false;
        if (root->left) {
            if (isZero(root->left)) {
                root->left = nullptr;
            }
            else {
                is0 = false;
            }
        }
        if (root->right) {
            if (isZero(root->right)) {
                root->right = nullptr;
            }
            else {
                is0 = false;
            }
        }
        return is0;
    }
public:
    TreeNode* pruneTree(TreeNode* root) {
        if (isZero(root))
            root = nullptr;
        return root;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/125918905