【Day 79 】2024-06-25 - 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

[hillsonziqiu]

思路

递归

代码

/*
 * @lc app=leetcode.cn id=814 lang=javascript
 *
 * [814] 二叉树剪枝
 */

// @lc code=start
/**
 * 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;
};
// @lc code=end

复杂度分析

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

[lxy1108]

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

[luzhaofeng]

class Solution:
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if (not root): return
        if (not root.left) and (not root.right):
            return root if root.val==1 else None
        # 处理左子树
        root.left = self.pruneTree(root.left)
        # 处理右子树
        root.right = self.pruneTree(root.right)
        if root.val==1 or (root.left or root.right):
            return root
        # 否则 说明左右节点都是空 并且root.val==0
        return None

[xy147]

js代码

var pruneTree = function (root) {
  function dfs(root) {
    if (!root) return 0;
    const l = dfs(root.left);
    const r = dfs(root.right);
    if (l == 0) root.left = null;
    if (r == 0) root.right = null;
    return root.val + l + r;
  }
  ans = new TreeNode(-1);
  ans.left = root;
  dfs(ans);
  return ans.left;
};

复杂度分析

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

[Dtjk]

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