【Day 79 】2021-11-27 - 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

[HondryTravis]

思路

后续遍历剪枝

代码

/**
 * 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 postTraverse = (root) => {
        if (!root) return null;

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

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

    return postTraverse(root);
};

复杂度分析

时间复杂度 O(n)

空间复杂度 O(1)

[Zhang6260]

JAVA版本

思路：

主要考察数的二种遍历方式，递归和非递归的方式，然后再具体确定是哪一种遍历，由题意可得是考察树的后序遍历。

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        //就是考察树的遍历  然后树的遍历有二种方式 
        //方法一  使用递归的方式
        if(root==null)return null;
        TreeNode left = pruneTree(root.left);
        TreeNode right = pruneTree(root.right);
        if(left==null){
            root.left = null;
        }
        if(right==null){
            root.right = null;
        }
        if(root.val==0&&left==null&&right==null){
            return null;
        }else{
            return root;
        }
    }
}

//套用模板即可
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        //就是考察树的遍历  然后树的遍历有二种方式 
        //方法二 使用非递归的方式对树进行遍历【使用哪一种遍历方式呢？？】
        if(root==null)return null;
        TreeNode res = root;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.right==null||root.right==prev){
                if(root.left!=null&&root.left.val==-1){
                    root.left=null;
                }
                if(root.right!=null&&root.right.val==-1){
                    root.right = null;
                }
                if(root.val==0&&root.left==null&&root.right==null){
                    root.val=-1;
                }
                prev = root;
                root = null;
            }else{
                stack.push(root);
                root = root.right;
            }
        }
        return res.val==-1?null:res;
    }
}

[nonevsnull]

思路

• 拿到题的直觉解法
  • 剪枝的形象化

AC

代码

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

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

        root.left = l;
        root.right = r;

        return l != null || r != null || root.val == 1?root:null;
    }
}

复杂度

time: O(N) space: O(H)

[shamworld]

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]

/**
 * 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
}

[mokrs]

TreeNode* pruneTree(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }

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

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

[HouHao1998]

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

    public boolean containsOne(TreeNode node) {
        if (node == null) return false;
        boolean a1 = containsOne(node.left);
        boolean a2 = containsOne(node.right);
        if (!a1) node.left = null;
        if (!a2) node.right = null;
        return node.val == 1 || a1 || a2;
    }
}

[jaysonss]

思路

判断root是否被裁剪的条件 cut(root.left) && cut(root.right) && root.val == 0

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

• 时间复杂度： O(n), 本质上是穷举，n为节点个数
• 空间复杂度：O(h), h为树的高度

[KennethAlgol]

class Solution {
public:
    int dfs(TreeNode* root) {
        if(!root) return 0;
        auto l = dfs(root -> left);
        auto r = dfs(root -> right);
        if(!l) root -> left = nullptr;
        if(!r) root -> right = nullptr;
        return root -> val + l + r;
    }
    TreeNode* pruneTree(TreeNode* root) {
        return dfs(root) != 0 ? root : nullptr;
    }
};

[user1689]

题目

https://leetcode-cn.com/problems/binary-tree-pruning/

思路

DFS

python3

# 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:
                return None

            leftNode = dfs(root.left)
            rightNode = dfs(root.right)
            if not leftNode:
                root.left = None
            if not rightNode:
                root.right = None

            return root.val == 1 or leftNode or rightNode

        return root if dfs(root) else None

复杂度分析

• time N
• space H

相关题目

1. 待补充

[Mrhero-web]

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

}

[ymkymk]

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

public boolean containsOne(TreeNode node) {
    if (node == null) return false;
    boolean a1 = containsOne(node.left);
    boolean a2 = containsOne(node.right);
    if (!a1) node.left = null;
    if (!a2) node.right = null;
    return node.val == 1 || a1 || a2;
}

}

时间复杂度：O(N)，其中 NN 是树中节点的个数。

空间复杂度：O(H)，其中 HH 是树的高度，为我们在递归时使用的栈空间大小

[Yufanzh]

Intuition

Recursive approach to trim binary tree.

1. check when there is only one node
2. find the recursive condition
3. find return condition

Algorithm in python3

# 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]:
        # recursive approach
        if not root: return 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
        else:
            return None

Complexity Analysis

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

[machuangmr]

代码

class Solution {
    /**  将root节点的树进行剪枝
     */
    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(H) H为数的高度

[ysy0707]

思路：递归+剪枝

class Solution {
    //特判：如果root为空，返回空
    //把root.left和root.right都放到pruneTree方法里去除一下不含1的子树，返回新的root.left和新的root.right
    //只要当前节点值为1或者左子树存在或者右子树存在，当前节点就可以保留，返回root；否则，返回空
    public TreeNode pruneTree(TreeNode root) {
        if(root == null){
            return null;
        }
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        return root.val == 1 || root.left != null || root.right != null? root: null;
    }
}

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

[leo173701]

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

[kkwu314]

思路

递归

代码

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

复杂度

时间：O(N)

空间：O(H), height of tree

[BreezePython]

思路

DFS

代码

class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        def dfs(node):
            if not node:
                return True
            v1 = dfs(node.left)
            v2 = dfs(node.right)
            if v1:
                node.left = None
            if v2:
                node.right = None
            return node.val == 0 and v1 and v2

        return None if dfs(root) else root

复杂度

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

[heyqz]

# 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 None
            node.left, node.right = dfs(node.left), dfs(node.right)
            if node.left or node.right:
                return node
            else:
                return node if node.val == 1 else None

        return dfs(root)

[A-PolarBear]

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

[biscuit279]

思路：递归

# 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 ContainOne(node):
            if not node:
                return None
            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
        if ContainOne(root):
            return root
        else:
            return None

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

[Moin-Jer]

思路

---

递归

代码

---

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

    public boolean containsOne(TreeNode node) {
        if (node == null) return false;
        boolean a1 = containsOne(node.left);
        boolean a2 = containsOne(node.right);
        if (!a1) node.left = null;
        if (!a2) node.right = null;
        return node.val == 1 || a1 || a2;
    }
}

复杂度分析

---

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

[revisegoal]

Note

二叉树，用dfs中序遍历，通过可行性剪枝，判断是否为0叶节点，若是则改为null

Code

/**
 * 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 dfs(root);
    }

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

Complexity

• time：O(n)，dfs要遍历所有节点，n为节点数
• space：O(n)，递归函数空间复杂度看堆栈空间，每次递归使用O(1)空间，则n次递归使用O(n)空间

[Richard-LYF]

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

[bingyingchu]

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

        if containsOne(root):
            return root
Time/Space: O(n)

[wangyifan2018]

# 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

[ChenJingjing85]

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

[for123s]

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        return containOne(root)?root:nullptr;
    }

    bool containOne(TreeNode* root){
        if(!root) return false;
        bool lc=containOne(root->left);
        bool rc=containOne(root->right);
        if(!lc) root->left=nullptr;
        if(!rc) root->right=nullptr;
        return (root->val==1) || lc || rc;
    }
};

[chakochako]

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

[erik7777777]

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

[yj9676]

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

    public boolean containsOne(TreeNode node) {
        if (node == null) return false;
        boolean a1 = containsOne(node.left);
        boolean a2 = containsOne(node.right);
        if (!a1) node.left = null;
        if (!a2) node.right = null;
        return node.val == 1 || a1 || a2;
    }
}

[joriscai]

思路

• 后序遍历
• 递归遍历树，并对左右子树重新赋值
• 赋值时判断节点是否为叶子节点，值为0。若是则返回空
• 由于递归是到叶子节点再回根节点，判断时从叶子节点层开始，一层一层的剪掉

代码

javascript

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

  // 当叶子节点为0时，则删除该节点
  if (root.val === 0 && !root.left && !root.right) {
    return null
  }
  return root
};
// @lc code=end

复杂度分析

• 时间复杂度：O(n)，遍历整个树
• 空间复杂度：O(h)，只有递归占用空间，h为树高

[Zhi22]

思路：后序遍历

补卡以便于进度管理

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

            left = containOne(root.left)
            right = containOne(root.right)

            if not left: root.left = None
            if not right: root.right = None

            return root.val == 1 or left or right

        return root if containOne(root) else None

[L-SUI]

/**

• 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) {

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

};

[liudi9047]

class Solution { public: int dfs(TreeNode root) { if(!root) return 0; auto l = dfs(root -> left); auto r = dfs(root -> right); if(!l) root -> left = nullptr; if(!r) root -> right = nullptr; return root -> val + l + r; } TreeNode pruneTree(TreeNode* root) { return dfs(root) != 0 ? root : nullptr; } };

[hellowxwworld]

代码

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

    if (root->left)
        pruneTrees(root->left);
    if (root->right)
        pruneTrees(root->right);

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

    return root;
}