【Day 79 】2023-01-18 - 814 二叉树剪枝

[azl397985856]

814 二叉树剪枝

入选理由

暂无

题目地址

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]

示例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

[whoam-challenge]

class Solution: def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if root is None: return None root.left = self.pruneTree(root.left) root.right = self.pruneTree(root.right) if root.left is None and root.right is None and root.val == 0: return None return root

[snmyj]

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(root==nullptr) return nullptr;
        if(root->val==0){
            if(root->left!=nullptr)
            {pruneTree(root->left);

            }
            if(root->right!=nullptr)
            {pruneTree(root->right);
            return root;}
            else return nullptr;
        }

        else if(root->val==1){
            pruneTree(root->left);
            pruneTree(root->right);
            return root;
            }

        return root;
    }
};

[Abby-xu]

# 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]:
        def dfs(node):
            if not node: return True
            left, right = dfs(node.left), dfs(node.right)
            if left: node.left = None
            if right: node.right = None
            return left and right and node.val == 0

        return root if not dfs(root) else None

[Ryanbaiyansong]

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]:

root

    def dfs(node):
        if node is None:
            return None, 0

        left, l_ones = dfs(node.left)
        right, r_ones = dfs(node.right)
        if node.val == 1:
            if l_ones == 0:
                node.left = None
            if r_ones == 0:
                node.right = None 
            return node, 1 + l_ones + r_ones
        elif node.val == 0:
            ones = 0
            if l_ones == 0:
                node.left = None 
            if r_ones == 0:
                node.right = None

            if not node.left and not node.right:
                return None, 0
            else:
                return node, l_ones + r_ones

    node, _ = dfs(root)
    return node

[Alexno1no2]

# 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
#  思路
#  目的是剪掉所有全是0的分枝，
#  可以递归看子树是否都为0，如果子树都为0即节点置为空; 子树都为空且自身是0就代表该节点可以被剪掉，返回空；
#  否则返回递归剪枝后的左子树和右子树构成的新树。

class Solution:
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        left, right = self.pruneTree(root.left), self.pruneTree(root.right)
        return None if not root.val and not left and not right else TreeNode(root.val, left,right)

[FlipN9]

/**
    Recursion

    N 为二叉树的节点个数
    TC: O(N)    每个节点都需要遍历一次
    SC: O(N)    递归的深度最多为 O(N)
*/
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null)
            return null;
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left == null && root.right == null && root.val == 0)
            return null;
        return root;
    }
}

[bookyue]

code

    public TreeNode pruneTree(TreeNode root) {
        if (root == null) return null;

        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);

        return (root.val == 0 && root.left == null && root.right == null) ? null : root;
    }

[Elsa-zhang]

# 814 二叉树剪枝
''' 
'''
# 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]):
        if root==None: 
            return None
        root.left = self.pruneTree(root.left)
        root.right = self.pruneTree(root.right)
        if root.left is None and root.right is None and root.val == 0:
            return None
        return root

[tiandao043]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(root==nullptr)return nullptr;
        root->left=pruneTree(root->left);
        root->right=pruneTree(root->right);
        if(root->val==0 && root->left==nullptr && root->right==nullptr){
            return nullptr;
        }
        return root;        
    }
};

O(H) O(N)

[Jetery]

814. 二叉树剪枝

思路

递归处理, 从底向上依次剪去值为0的叶子节点

代码 (cpp)

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if (root == nullptr) return root;
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        // 值为 0 的叶子节点
        if (root->left == nullptr && root->right == nullptr && root->val == 0) 
            return nullptr;
        return root;
    }
};

复杂度分析

• 时间复杂度：O(height)
• 空间复杂度：O(n)

[klspta]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        return process(root);
    }

    private TreeNode process(TreeNode root){
        if(root == null){
            return null;
        }

        root.left = process(root.left);
        root.right = process(root.right);

        if(root.val == 0 && root.left == null && root.right == null){
            return null;
        }

        return root;
    }
}

[RestlessBreeze]

code

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if (!root) {
            return nullptr;
        }
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        if (!root->left && !root->right && !root->val) {
            return nullptr;
        }
        return root;
    }   
};

[paopaohua]

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null)
            return null;
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left == null && root.right == null && root.val == 0)
            return null;
        return root;
    }
}

[mayloveless]

思路

递归，如果不包含1，则子树赋值为null

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var pruneTree = function(root) {
    function containsOne(node) {
        if (node == null) return false;
        const a1 = containsOne(node.left);
        const a2 = containsOne(node.right);
        if (!a1) node.left = null;
        if (!a2) node.right = null;
        return node.val == 1 || a1 || a2;
    }
    return containsOne(root) ? root : null;
};

复杂度

时间O(n) 空间O（n）

[Elon-Lau]

/**

• Definition for a binary tree node.
• function TreeNode(val) {
• this.val = val;
• this.left = this.right = null;
• } */ /**
• @param {TreeNode} root
• @return {TreeNode} */ var pruneTree = function(root) { function containsOne(node) { if (node == null) return false; const a1 = containsOne(node.left); const a2 = containsOne(node.right); if (!a1) node.left = null; if (!a2) node.right = null; return node.val == 1 || a1 || a2; } return containsOne(root) ? root : null; };