Skip to content

814. Binary Tree Pruning

难度: Medium

刷题内容

原题连接 * https://leetcode-cn.com/problems/binary-tree-pruning/

内容描述 ``` 给定二叉树根结点 root ,此外树的每个结点的值要么是 0,要么是 1。

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

( 节点 X 的子树为 X 本身,以及所有 X 的后代。)

示例1: 输入: [1,null,0,0,1] 输出: [1,null,0,null,1] ```

解题方案

思路 1

遍历二叉树,切除左右子树中无1的子树。
bool dfs(TreeNode* root){
    if(root==NULL)
        return false;
    bool left = dfs(root->left);
    bool right = dfs(root->right);
    if(left==false)
        root->left=NULL;
    if(right==false)
        root->right=NULL;
    return root->val==1||left||right;
}
TreeNode* pruneTree(TreeNode* root) {
    dfs(root);
    return root;
}


回到顶部