leetcode814. 二叉树剪枝(java)

这篇具有很好参考价值的文章主要介绍了leetcode814. 二叉树剪枝(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

leetcode814. 二叉树剪枝

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/binary-tree-pruning

题目描述

给你二叉树的根结点 root ,此外树的每个结点的值要么是 0 ,要么是 1 。
返回移除了所有不包含 1 的子树的原二叉树。
节点 node 的子树为 node 本身加上所有 node 的后代。

示例1:
leetcode814. 二叉树剪枝(java)
输入:root = [1,null,0,0,1]
输出:[1,null,0,null,1]
解释:
只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。

示例2:
leetcode814. 二叉树剪枝(java)
输入:root = [1,0,1,0,0,0,1]
输出:[1,null,1,null,1]

示例3:
leetcode814. 二叉树剪枝(java)
输入:root = [1,1,0,1,1,0,1,0]
输出:[1,1,0,1,1,null,1]

提示:
树中节点的数目在范围 [1, 200] 内
Node.val 为 0 或 1

DFS 深度优先遍历

首先确定边界条件,当输入为空时,即可返回空。然后对左子树和右子树分别递归进行递归操作。递归完成后,当这三个条件:左子树为空,右子树为空,当前节点的值为 0,同时满足时,才表示以当前节点为根的原二叉树的所有节点都为 0,需要将这棵子树移除,返回空。有任一条件不满足时,当前节点不应该移除,返回当前节点。

/**
 * 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);
    }
	/**
	* 深度优先遍历 
	* DFS
	*/
    public TreeNode process(TreeNode root ){
    	//base case 直接返回
        if(root == null){
            return null;
        }
        root.left = process(root.left);
        root.right = process(root.right);
        //当前为叶子节点时,且值为0 时,可以直接剪枝,返回null 就等于剪掉了
         if(root.val == 0 && root.left == null && root.right == null){  
            return null ;
        }
        return root;
    }
 )

二叉树专题

leetcode257. 二叉树的所有路径

leetcode111. 二叉树的最小深度

leetcode2385. 感染二叉树需要的总时间

leetcode222. 完全二叉树的节点个数

leetcode199. 二叉树的右视图

leetcode–从二叉搜索树到更大和树

根据前序和后序遍历构造二叉树文章来源地址https://www.toymoban.com/news/detail-499219.html

到了这里,关于leetcode814. 二叉树剪枝(java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍     文章目录         1.0 从前序与中序遍历序列来构造二叉树         1.1 实现从前序与中序遍历序列来构造二叉树思路            1.2 代码实现从前序与中序遍历序列来构造二叉树         2.0 从中序

    2024年02月05日
    浏览(77)
  • leetcode199. 二叉树的右视图(java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/binary-tree-right-side-view 给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例1: 输入: [1,2,3,null,5,null,4] 输出: [1,3,4] 示例 2: 输入: [1,null,3] 输出: [1,3] 示例 3: 输入

    2024年02月09日
    浏览(33)
  • leetcode111. 二叉树的最小深度(java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/minimum-depth-of-binary-tree 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。 示例1: 输入:root = [3,9,20,null,null,15,7] 输出:2 示例2: 输入:

    2024年02月09日
    浏览(36)
  • Java LeetCode篇-二叉树经典解法(实现:判断平衡二叉树、找两个节点最近的祖先等)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍     文章目录         1.0 平衡二叉树         1.1 实现判断平衡二叉树的思路         1.2 代码实现判断平衡二叉树         2.0 二叉树的层序遍历         2.1 实现二叉树层序遍历的思路          2.2

    2024年02月05日
    浏览(51)
  • 【Py/Java/C++三种语言详解】LeetCode每日一题240216【二叉树BFS】LeetCode103、二叉树的层序遍历II

    有LeetCode交流群/华为OD考试扣扣交流群可加: 948025485 可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题 绿色聊天软件戳 od1336 了解算法冲刺训练 LeetCode103、二叉树的锯齿形层序遍历 给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进

    2024年02月20日
    浏览(40)
  • Java LeetCode篇-深入了解二叉树经典解法(三种方式实现:获取二叉树的最大深度)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 对称二叉树         1.1 判断对称二叉树实现思路         1.2 代码实现:判断对称二叉树         2.0 二叉树的最大深度         2.1 使用递归实现获取二叉树的最大深度思

    2024年02月05日
    浏览(77)
  • 《剑指 Offer》专项突破版 - 面试题 47 : 二叉树剪枝(C++ 实现)

    题目链接 :LCR 047. 二叉树剪枝 - 力扣(LeetCode) 题目 : 一棵二叉树的所有节点的值要么是 0 要么是 1,请剪除该二叉树中 所有节点的值全都是 0 的子树 。例如,在剪除下图 (a) 中二叉树中所有节点值都为 0 的子树之后的结果如下图 (b) 所示。 分析 : 首先分析哪些子树会被

    2024年02月20日
    浏览(39)
  • 【深度优先】【广度优先】Leetcode 104 二叉树的最大深度 Leetcode 111 二叉树的最小深度 Leetcode 110 平衡二叉树

    二叉树节点的深度: 指从根节点到该节点的最长简单路径边的条数或者节点数 (取决于深度从0开始还是从1开始) 二叉树节点的高度: 指从该节点到叶子节点的最长简单路径边的条数后者节点数 (取决于高度从0开始还是从1开始) 【前序求的是深度,后序求的是高度】 -

    2024年02月19日
    浏览(53)
  • 二叉树OJ题:LeetCode--965.单值二叉树

    朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第965道二叉树OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏: 数据结构与算法 个  人  主  页  : stackY、 C 语 言 专 栏 : C语言:从入门到精通 ​ Le

    2024年02月12日
    浏览(49)
  • 二叉树OJ题:LeetCode--101.对称二叉树

    朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第144道二叉树OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏: 数据结构与算法 个  人  主  页  : stackY、 C 语 言 专 栏 : C语言:从入门到精通 LeetCo

    2024年02月13日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包