【Day 79 】2023-05-03 - 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

[Abby-xu]

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

[Zoeyzyzyzy]

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

[LIMBO42]

bool dfs(TreeNode* root) {
        if(root == nullptr) return false;
        bool flag1 = dfs(root->left);
        bool flag2 = dfs(root->right);
        // false 代表不包含1
        // true 代表包含1
        if(flag1 == false) {
            root->left = nullptr;
        }
        if(flag2 == false) {
            root->right = nullptr;
        }
        if(!flag1 && !flag2 && root->val != 1) return false;
        return true;
    }
    TreeNode* pruneTree(TreeNode* root) {
        // 左右根
        bool flag = dfs(root);
        if(flag == false) return nullptr;
        return root;
    }

[NorthSeacoder]

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var pruneTree = function (root) {

    const dfs = (node) => {
        if (!node) return null
        node.left = dfs(node.left)
        node.right = dfs(node.right)
        if (!node.left && !node.right && node.val === 0) return null;
        return node
    }

    return dfs(root)
};

[RestlessBreeze]

code

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

[snmyj]

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

        return root;
    }
};

[bookyue]

TC: O(n)
SC: O(n)

    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;
    }

[harperz24]

class Solution:
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        root.left = self.pruneTree(root.left)
        root.right = self.pruneTree(root.right)
        if not root.left and not root.right and root.val == 0:
            return None
        return root

[csthaha]

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var pruneTree = function(root) {
    if(!root) return null;
    root.left = pruneTree(root.left);
    root.right = pruneTree(root.right);
    if(root.val === 0 && !root.left && !root.right) return null;
    return root;
};

[chocolate-emperor]

/**
 * 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 root;

        root->left  = pruneTree(root->left);
        root->right = pruneTree(root->right);

        if(root->val == 0 ){
            if(root->left ==nullptr&&root->right==nullptr)  return nullptr;
        }

        return root;
    }
};

[zhangyu1131]

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        // 利用后序，先处理左右子树
        // 如果左子树全是0，left=null
        // 如果右子树全是0, right=null
        bool all_zero = postOrder(root);
        if (all_zero)
        {
            return nullptr;
        }

        return root;
    }

private:
    bool postOrder(TreeNode* root)
    {
        if (!root)
        {
            return true;
        }

        bool left_all_zero = postOrder(root->left);
        bool right_all_zero = postOrder(root->right);

        if (left_all_zero)
        {
            root->left = nullptr;
        }
        if (right_all_zero)
        {
            root->right = nullptr;
        }

        return left_all_zero && right_all_zero && root->val == 0;
    }
};

[Diana21170648]

思路

二叉树剪枝

class Solution:
      def pruneTree(self, root):
           def  containsOne(node):
                 if not node:return False
                  left = containsOne(node.left)
                  right = containsOne(node.right)
                  if not left: node.left = None
                  if not right: node.right = None
                  return node.val == 1or leftor right

       return root  if containsOne(root)else None

**复杂度分析**
- 时间复杂度：O(H)，其中 H为树的深度
- 空间复杂度：O(N),N是树节点的个数

[joemonkeylee]

思路

递归

代码

    function pruneTree(root: TreeNode | null): TreeNode | null {
        if (root == null) return null
        root.left = pruneTree(root.left)
        root.right = pruneTree(root.right)
        if (root.left != null || root.right != null) return root
        return root.val == 0 ? null : root
    };

复杂度分析

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

[sye9286]

思路

用递归，当左右子树都为空且当前节点为 0 时，移除这棵子树

代码

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

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[JasonQiu]

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

Time: O(n) Space: O(h)

[kangliqi1]

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;

}

[lp1506947671]

class Solution(object):
    def pruneTree(self, root):
        def containsOne(node):
            if not node: return False
            left = containsOne(node.left)
            right = containsOne(node.right)
            if not left: node.left = None
            if not right: node.right = None
            return node.val == 1 or left or right

        return root if containsOne(root) else None

复杂度分析

• 空间复杂度：没有额外空间使用，因此空间复杂度就是递归栈的最大深度O(H)，其中 H 是树高。

• 时间复杂度：最坏情况就是所有节点都剪掉了，因此时间复杂度是O(N)，其中 N 是树节点的个数。

[X1AOX1A]

class Solution(object): def pruneTree(self, root): def containsOne(node): if not node: return False left = containsOne(node.left) right = containsOne(node.right) if not left: node.left = None if not right: node.right = None return node.val == 1 or left or right

    return root if containsOne(root) else None

[tzuikuo]

思路

代码

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(!ifhasone(root)) return NULL;
        else{
            traversal(root);
        }
        return root;
    }
    void traversal(TreeNode* root){
        if(!root) return;
        else{
            if(!ifhasone(root->left)) root->left=NULL;
            if(!ifhasone(root->right)) root->right=NULL;
        }
        traversal(root->left);
        traversal(root->right);
    }
    bool ifhasone(TreeNode* tempnode){
        if(!tempnode) return false;
        if(tempnode->val==1) return true;
        else{
            return ifhasone(tempnode->left)||ifhasone(tempnode->right);
        }
    }
};

复杂度分析 -待定

[jackgaoyuan]

func pruneTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Left, root.Right = pruneTree(root.Left), pruneTree(root.Right)
    if root.Left == nil && root.Right == nil && root.Val == 0 {
        return nil
    }
    return root
}

[Fuku-L]

代码

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;
    }
}

复杂度分析

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

[Lydia61]

814. 二叉树剪枝

思路

递归，二叉树剪枝

代码

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

[Jetery]

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

[FireHaoSky]

思路：递归

代码：python

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

复杂度分析：

"""
时间复杂度：O(n)
空间复杂度：O(n)
"""

[kofzhang]

思路

深度优先搜索

代码

class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:

        def dfs(node):
            if not node:
                return None
            node.left = dfs(node.left)
            node.right = dfs(node.right)
            if node.val or node.left or node.right:
                return node
            else:
                return None

        return dfs(root)

[chanceyliu]

代码

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}

function pruneTree(root: TreeNode | null): TreeNode | null {
  if (!root) {
    return null;
  }
  root.left = pruneTree(root.left);
  root.right = pruneTree(root.right);
  if (!root.left && !root.right && root.val === 0) {
    return null;
  }
  return root;
};

复杂度分析

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