leetcode-814:二叉树剪枝

简介: leetcode-814:二叉树剪枝

题目

题目连接

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

解题

方法一:后序遍历

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(!root) return nullptr;
        TreeNode* left=pruneTree(root->left);
        TreeNode* right=pruneTree(root->right);
        if(!left) root->left=nullptr;
        if(!right) root->right=nullptr;
        if(root->val==0&&!(left||right)) return nullptr;
        return root;
    }
};
相关文章
|
2月前
|
决策智能
【LeetCode 50】77.组合(优化、剪枝操作)
【LeetCode 50】77.组合(优化、剪枝操作)
16 2
|
2月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
20 2
|
2月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
18 2
|
2月前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
16 2
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
20 0
|
2月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
15 0
|
2月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
17 0
|
2月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
20 0
|
2月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
19 0
|
4月前
|
存储 算法
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
文章深入探讨了二叉树的层序遍历方法,并展示了如何通过队列实现层序遍历的算法逻辑,同时指出掌握层序遍历技巧可以帮助解决LeetCode上的多道相关题目。
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题