azl397985856 commented 2 years ago

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

yetfan commented 2 years ago

思路递归： 1.边界 2.左子树 3.右子树 4.自己

代码

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 root.left == None and root.right == None and root.val == 0:
            return None
        return root

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

zwx0641 commented 2 years ago

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if (dfs(root)) {
            root = nullptr;
        }
        return root;
    }

    bool dfs(TreeNode* root) {
        if (root == nullptr) return true;

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

        bool l = dfs(root->left);
        bool r = dfs(root->right);
        if (l) root->left = nullptr;
        if (r) root->right = nullptr;

        return l && r && root->val == 0;
    }
};

charlestang commented 2 years ago

思路

递归。

我们递归的对左子树做剪枝，和右子树做剪枝。

如果左右子树都是 None，而且 root 值为 0，那么整个树都被剪掉。

否则的话，将 root 的左右子树替换成剪枝后的结果返回即可。

代码

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

时间复杂度 根据主定理 T(n) = 2 T(n/2) + 1，复杂度是 O(n)

feifan-bai commented 2 years ago

思路 1.递归

代码

 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)
空间复杂度：O(N)

zhangzz2015 commented 2 years ago

思路

后序遍历，处理左子树，处理右子树，如果左右子树都为空，则check 当前root->val 是否等于0，是则删除当前节点，返回空给上一层。时间复杂度为 O(n)，空间复杂度为 O(n)，递归深度。

关键点

代码

语言支持：C++

C++ Code:


/**
 * 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) {

        return dfs(root); 

    }

    TreeNode* dfs(TreeNode* root)
    {
        if(root==NULL)
            return NULL; 

        root->left = dfs(root->left); 
        root->right = dfs(root->right); 
        if(root->left ==NULL &&  root->right==NULL && root->val ==0)
            return NULL; 
        return root;         

    }
};

ZhangNN2018 commented 2 years ago

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def pruneTree(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: Optional[TreeNode]
        """
        def dfs(r):
            if r.left  and dfs(r.left):
                r.left  = None   #左
            if r.right and dfs(r.right):
                r.right = None   #右
            if r.val == 0 and not r.left and not r.right: #根
                return True

        if not root: return root    
        return None if dfs(root) else root

QinhaoChang commented 2 years ago

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

    return root if containsOne(root) else None

CoreJa commented 2 years ago

思路

DFS：设计递归函数为本身就能返回按要求剪枝后的树，对自己的左子树和右子树分别递归调用子过程，并把左右子树返回为调用后的返回值。左右子树都已经修剪完成了，如果左右子树存在，或当前节点为1，则说明这个节点不会被剪掉，返回当前节点，反之返回None。复杂度$O(n)$

代码

class Solution:
    # DFS：设计递归函数为本身就能返回按要求剪枝后的树，对自己的左子树和右子树分别递归调用子过程，并把左右子树返回为调用后的
    # 返回值。左右子树都已经修剪完成了，如果左右子树存在，或当前节点为1，则说明这个节点不会被剪掉，返回当前节点，反之返回
    # None。复杂度$O(n)$
    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 root.left or root.right or root.val == 1:
            return root
        return None

yijing-wu commented 2 years ago

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if(helper(root) == false) {
            return null;
        }
        return root;
    }

    private boolean helper(TreeNode node) {
        if(node == null) return false;
        // node.val == 0
        boolean checkLeft = helper(node.left);
        boolean checkRight = helper(node.right);
        if(node.left != null && checkLeft == false) {
            node.left = null;
        }
        if(node.right != null && checkRight == false) {
            node.right = null;
        }        
        return checkLeft || checkRight || node.val == 1;
    }
}

Tesla-1i commented 2 years ago

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

yan0327 commented 2 years ago

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

james20141606 commented 2 years ago

Day 79: 814. Binary Tree Pruning (DFS, binary tree, recursion)

Problem Link
- 814. Binary Tree Pruning
Ideas
- use recursive pruning or use post-order traversal
Complexity: hash table and bucket
- Time: O(N)
- Space: O(H)
Code

class Solution:
    def pruneTree(self, root):
        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

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

other resources:
- https://leetcode-cn.com/problems/binary-tree-pruning/solution/er-cha-shu-jian-zhi-by-leetcode/

C2tr commented 2 years ago

class Solution: def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: def dfs(r): if r.left and dfs(r.left): r.left = None #左 if r.right and dfs(r.right): r.right = None #右 if r.val == 0 and not r.left and not r.right: #根 return True

    if not root: return root    
    return None if dfs(root) else root

1149004121 commented 2 years ago

二叉树剪枝

思路

剪枝。如果某节点的左节点被剪，右节点被剪，且该节点值为0则也要被剪。

代码

var pruneTree = function(root) {
    return dfs(root) === 0 ? null : root;

    function dfs(root){
        if(root === null) return 0;
        let val1 = dfs(root.left);
        let val2 = dfs(root.right);
        if(val1 === 0) root.left = null;
        if(val2 === 0) root.right = null;
        return (val1 | val2 | root.val);
    }
};

复杂度分析

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

xuhzyy commented 2 years ago

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def pruneTree(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: Optional[TreeNode]
        """
        if not root:
            return None

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

ZJP1483469269 commented 2 years ago

class Solution:
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node):
            if not node:
                return False
            l = dfs(node.left)
            r = dfs(node.right)
            if not l:
                node.left = None
            if not r:
                node.right = None
            return node.val == 1 or l or r 
        return root if dfs(root) else None

z1ggy-o commented 2 years ago

思路

post-order traverse

对于一个节点，它是否能够被移除是被它的子节点决定的。这个特性适用于后序遍历。

代码

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 == 0)
            return nullptr;
        return root;
    }
};

复杂度分析

时间：O(n), 遍历整棵树
空间：O(1)

callmeerika commented 2 years ago

思路

dfs

代码

const findOne = (node) => {
  if (node === null) return null;
  node.left = findOne(node.left);
  node.right = findOne(node.right);
  if(node.val === 1 || findOne(node.left) || findOne(node.right)) {
    return node;
  } else {
    return null;
  }
}

var pruneTree = function(root) {
  return findOne(root);
};

复杂度

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

herbertpan commented 2 years ago

思路

标准二叉树思维

code

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        boolean isTheRootValid = helper(root);

        return isTheRootValid ? root : null;
    }

    private boolean helper(TreeNode node) {
        if (node == null) {
            return false;
        }

        boolean isLeftChildValid = helper(node.left);
        if (!isLeftChildValid) {
            node.left = null;
        }

        boolean isRightChildValid = helper(node.right);
        if (!isRightChildValid) {
            node.right = null;
        }

        if (!isLeftChildValid && !isRightChildValid && node.val == 0) {
            return false;
        }

        return true;
    }
}

complexity

time: O(n)
space: O(height)

Tao-Mao commented 2 years ago

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        return containsOne(root) ? root : null;
    }

    public boolean containsOne(TreeNode node) {
        if (node == null) return false;

        // Check if any node in the left subtree contains a 1.
        boolean leftContainsOne = containsOne(node.left);

        // Check if any node in the right subtree contains a 1.
        boolean rightContainsOne = containsOne(node.right);

        // If the left subtree does not contain a 1, prune the subtree.
        if (!leftContainsOne) node.left = null;

        // If the right subtree does not contain a 1, prune the subtree.
        if (!rightContainsOne) node.right = null;

        // Return true if the current node, its left or right subtree contains a 1.
        return node.val == 1 || leftContainsOne || rightContainsOne;
    }
}

LannyX commented 2 years ago

思路

剪枝

代码

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

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

复杂度分析

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

haixiaolu commented 2 years ago

class Solution:
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node):
            if not node:
                return False
            leftSub = dfs(node.left)
            rightSub = dfs(node.right)
            if not leftSub:
                node.left = None
            if not rightSub:
                node.right = None

            return node.val == 1 or leftSub or rightSub
        return root if dfs(root) else None

cszys888 commented 2 years ago

# 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):
            ret = node.val == 0
            if node.left:
                left_ret = dfs(node.left)
                if left_ret:
                    node.left = None
                ret = ret and left_ret
            if node.right:
                right_ret = dfs(node.right)
                if right_ret:
                    node.right = None
                ret = ret and right_ret
            return ret
        ret = dfs(root)
        return None if ret else root

time complexity: O(n), n is number of nodes in the whole tree space complexity: O(h), h is height of the tree

zhiyuanpeng commented 2 years ago

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 root.left == None and root.right == None and root.val == 0:
            return None
        return root

HWFrankFung commented 2 years ago

Codes


var pruneTree = function(root) {
    if (!root) {
        return null;
    }

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

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

    root.left = left;
    root.right = right;

    return root;
};

tongxw commented 2 years ago

思路

后序遍历，从叶子节点开始把节点是否为0的信息向上传递，同时剪枝

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        return isAllZeros(root) ? null : root;
    }

    private boolean isAllZeros(TreeNode root) {
        if (root == null) {
            return true;
        }

        boolean isLeftAllZeros = isAllZeros(root.left);
        boolean isRightAllZeros = isAllZeros(root.right);

        // prune
        if (isLeftAllZeros) {
            root.left = null;
        }
        if (isRightAllZeros) {
            root.right = null;
        }

        // return to parent
        if (root.val == 0 && isLeftAllZeros && isRightAllZeros) {
            return true;
        } else {
            return false;
        }
    }
}

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

hdyhdy commented 2 years ago

func pruneTree(root *TreeNode) *TreeNode {
    return deal(root)
}

func deal(node *TreeNode) *TreeNode {
    if node == nil {
        return nil
    }
    node.Left = deal(node.Left)
    node.Right = deal(node.Right)
    if node.Left == nil && node.Right == nil && node.Val == 0 {
        return nil
    }
    return node 
}

alongchong commented 2 years ago

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

KennethAlgol commented 2 years ago


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

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

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

        root.left = left;
        root.right = right;

        return (left != null || right != null || root.val == 1) ? root : null;
    }
}

falconruo commented 2 years ago

思路:

后序遍历

复杂度分析:

时间复杂度: O(N)，N为树的节点数
空间复杂度: O(logN)

代码(C++):

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if (!root) return nullptr;

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

        return (!root->left && !root->right && root->val == 0) ? nullptr : root;
    }
};

wenlong201807 commented 2 years ago

代码块


var pruneTree = function (root) {
  function dfs (root) {
    if (root == null)
      return 0;
    const l = dfs(root.left),
      r = dfs(root.right);
    if (l == 0)
      root.left = null;
    if (r == 0)
      root.right = null;
    return l + r + root.val;
  }
  return dfs(root) == 0 ? null : root
};

时间复杂度和空间复杂度

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

Richard-LYF commented 2 years ago

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 containsOne(node):
        if not node:
            return False
        a1 = containsOne(node.left)
        a2 = containsOne(node.right)
        if not a1:
            node.left = None 
        if not a2:
            node.right = None 
        return node.val == 1 or a1 or a2

    return root if containsOne(root) else None

on on

Toms-BigData commented 2 years ago

func pruneTree(root *TreeNode) *TreeNode {
    return deal(root)
}

func deal(node *TreeNode) *TreeNode {
    if node == nil {
        return nil
    }
    node.Left = deal(node.Left)
    node.Right = deal(node.Right)
    if node.Left == nil && node.Right == nil && node.Val == 0 {
        return nil
    }
    return node 
}

Aobasyp commented 2 years ago

思路递归

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)，时间复杂度：O(N)

declan92 commented 2 years ago

思路

1. dfs遍历二叉树;
2. 记录子树包含1的个数,如果个数为0,删除子树;

java

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        int count =dfs(root);
        if(count==0) return null;
        return root;

    }
    public int dfs(TreeNode root){
        int count = 0;
        if(root == null) return 0;
        if(root.val==1) count++;
        if(dfs(root.left)==0){
            root.left = null;
        }else{
            count += dfs(root.left);
        }
        if(dfs(root.right)==0){
            root.right = null;
        }else{
            count += dfs(root.right);
        }

        return count;
    }
}

时间:O(n),n为树的结点数空间:O(h),h为输的高度

Alexno1no2 commented 2 years ago

# 后序遍历树，
# 如果左侧返回True，就让左侧子树为None；
# 如果右侧返回True，就让右侧子树为None；
# 如果当前节点为0且无左右子树，就返回True
class Solution:
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(r):
            if r.left  and dfs(r.left):  
                r.left  = None   #左
            if r.right and dfs(r.right): 
                r.right = None   #右
            if r.val == 0 and not r.left and not r.right: #根
                return True
            return False

        # if not root: 
        #     return root    
        return None if dfs(root) else root

biscuit279 commented 2 years ago

思路:递归

class Solution(object):
    def pruneTree(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: Optional[TreeNode]
        """
        def ContainOne(node):
            if not node:
                return False
            left = ContainOne(node.left)
            right = ContainOne(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 ContainOne(root) else None

时间复杂度：O（h）空间复杂度：O（n）

xjhcassy commented 2 years ago

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

yinhaoti commented 2 years ago

# 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]:
        """
        Idea: 
            if root == 0 -> cut else return root
            cut left subtree
            cut right subtree
        TC: O(n)
        SC: O(logN) O(h)
        """

        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
            # print(node)
            return node.val == 1 or left or right
        return root if containsOne(root) else None

BiuBiuBangBoom commented 2 years ago

814. 二叉树剪枝

1 题目

链接：814. 二叉树剪枝

2 题目类型

二叉树
DFS

3 我的思路

一句话：后续遍历二叉树，判断其左右子树是否全0子树，是的话就令其指针指向nullptr

判断是否需要剪枝掉某中间节点的子树，取决于：

其左子树是否为全0子树
其右子树是否为全0子树
其本身的值是否为0

上面三个条件全部满足的话便可以剪掉该结点及其子树（令指针为nullptr）。

代码

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

private:
    bool dfs(TreeNode* root) {
        if (root == nullptr) { //空节点也需要剪掉
            return false;
        }
        bool hasleft = dfs(root->left);
        bool hasright = dfs(root->right);
        if (!hasleft) { //剪掉子树
            root->left = nullptr;
        }
        if (!hasright) {
            root->right = nullptr;
        }
        return hasleft || hasright || (root->val != 0); //上面三个条件缺一不可
    }
};

复杂度分析

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

4 启发

二叉树题目先判断空节点的时候。

Riuusee commented 2 years ago

思路

后序遍历，判断是否满足条件

代码

/**
 * 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) {
        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)
空间复杂度: O(1)

dahaiyidi commented 2 years ago

Problem

[814. 二叉树剪枝](https://leetcode-cn.com/problems/binary-tree-pruning/)

难度中等211

给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。

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

节点 node 的子树为 node 本身加上所有 node 的后代。

Note

只是在树遍历的基础上添加了一个过滤条件而已。

Complexity

时间O：N
空间O：H，为树的高度

Python

C++

/**
 * 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:
    bool is_zero(TreeNode* root){
        bool left = true;
        if(root->left){
            left = is_zero(root->left);
            if(left){
                root->left = NULL;
            }
        }

        bool right = true;
        if(root->right){
            right = is_zero(root->right);
            if(right){
                root->right = NULL;
            }
        }
        return root->val == 0 && left && right;
    }
    TreeNode* pruneTree(TreeNode* root) {
        bool res = is_zero(root);
        if(res){
            return nullptr;
        }
        return root;      

    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

ZacheryCao commented 2 years ago

idea

Prune + dfs

code

# 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(root):
            if not root.left and not root.right:
                return root.val == 1
            left = False
            right = False
            if root.left:
                left = dfs(root.left)
            if root.right:
                right = dfs(root.right)
            if not left:
                root.left = None
            if not right:
                root.right = None
            return root.val == 1 or left or right
        dummy = root
        if not dfs(dummy):
            return None
        return root

Complexity:

Space: O(H) Time: O(N)

shamworld commented 2 years ago

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

    return root;
};

guangsizhongbin commented 2 years ago

/**

Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
} / func pruneTree(root TreeNode) *TreeNode { if root == nil { return nil }

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

Hacker90 commented 2 years ago

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

return root;

};

xinhaoyi commented 2 years ago

814. 二叉树剪枝

题目

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

思路

用二叉树的后序遍历，如果一个结点本身值为0，且左右子树都为null，那么这个结点就是该被剪去的结点，把它置为null，之所以要用后序遍历，是因为我们要判断一个结点是否该被减去，必须要等它的左右子树都被剪枝完成后才能做决定。

代码

/**
 * 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) {
        TreeNode treeNode = deleteAssist(root);
        return treeNode;
    }

    public TreeNode deleteAssist(TreeNode node) {
        //中序遍历
        if (node == null) {
            return null;
        }

        node.left = deleteAssist(node.left);
        node.right = deleteAssist(node.right);

        //出口
        if (node.val == 0 && node.left == null && node.right == null) {
            node = null;
        }
        return node;
    }
}

复杂度分析

时间复杂度：o(n)

分析：因为树的每一个结点都要遍历一次

空间复杂度：o(n)

分析：因为每个结点都会生成一个函栈帧，所以一共是o(n)规模的辅助空间

kite-fly6618 commented 2 years ago

思路

后序遍历

代码

var pruneTree = function(root) {
  if (root == null) {
    return root;
  }
  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(1)

Jay214 commented 2 years ago

后续遍历

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var pruneTree = function(root) {
  // 判断非空情况
  if (root == null) {
    return root;
  }
  root.left = pruneTree(root.left);
  root.right = pruneTree(root.right);
  // 当左右节点都为空且当前节点的值为0的情况下，即可剪枝
  if (!root.left && !root.right && root.val == 0) {
    return null;
  }
  return root;
};

for123s commented 2 years ago

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

    TreeNode* pruneTree(TreeNode* root) {
        return dfs(root);  
    }
};

leetcode-pp / 91alg-6-daily-check

【Day 79 】2022-02-28 - 814 二叉树剪枝 #89

814 二叉树剪枝

入选理由

题目地址

前置知识

题目描述

思路

代码

思路

关键点

代码

思路

代码

Day 79: 814. Binary Tree Pruning (DFS, binary tree, recursion)

思路

代码

思路

代码

复杂度

思路

code

complexity

思路

代码

Codes

思路

代码块

时间复杂度和空间复杂度

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

on on

思路:递归

814. 二叉树剪枝

1 题目

2 题目类型

3 我的思路

代码

复杂度分析

4 启发

思路

代码

Problem

[814. 二叉树剪枝](https://leetcode-cn.com/problems/binary-tree-pruning/)

Note

Complexity

Python

C++

idea

code

Complexity:

814. 二叉树剪枝

题目

思路

代码

复杂度分析

思路

代码

复杂度

后续遍历