-
2020-02-07 15:31:18
LeetCode:1325. 删除给定值的叶子节点 题解:
给你一棵以 root 为根的二叉树和一个整数 target ,请你删除所有值为 target 的 叶子节点 。 注意,一旦删除值为 target 的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是 target ,那么这个节点也应该被删除。 也就是说,你需要重复此过程直到不能继续删除。 输入:root = [1,2,3,2,null,2,4], target = 2 输出:[1,null,3,null,4] 解释: 上面左边的图中,绿色节点为叶子节点,且它们的值与 target 相同(同为 2 ),它们会被删除,得到中间的图。 有一个新的节点变成了叶子节点且它的值与 target 相同,所以将再次进行删除,从而得到最右边的图。 输入:root = [1,3,3,3,2], target = 3 输出:[1,3,null,null,2] 输入:root = [1,2,null,2,null,2], target = 2 输出:[1] 解释:每一步都删除一个绿色的叶子节点(值为 2)。 输入:root = [1,1,1], target = 1 输出:[] 输入:root = [1,2,3], target = 1 输出:[1,2,3] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/delete-leaves-with-a-given-value 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
想查看图片就点一下链接吧思路简介:
- 递归好了,比较简洁
- 递归出口:结点为
NULL
- 先清理左子树与target相同的结点
- 再清理右子树与target相同的结点
- 如果root结点也是叶结点且与target的值相同,返回
NULL
show code:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* removeLeafNodes(TreeNode* root, int target) { if(root==NULL) return NULL; root->left=removeLeafNodes(root->left,target); root->right=removeLeafNodes(root->right,target); if(root->left==NULL&&root->right==NULL&&root->val==target) return NULL; return root; } };
更多相关内容 -
删除二叉树所有叶子节点
2020-05-02 19:16:44//删除二叉树中的所有叶子节点 void DeleteLev(BiTree T,BiTree f,bool flag){ if(T){//T is not NULL if(T->l){ DeleteLev(T->l,T,true); } if(T->r){ DeleteLev(...//删除二叉树中的所有叶子节点 void DeleteLev(BiTree T,BiTree f,bool flag){ if(T){//T is not NULL if(T->l){ DeleteLev(T->l,T,true); } if(T->r){ DeleteLev(T->r,T,false); }else{//T is a level node free(T); if(f){// T is not root if(flag)f->l = NULL; else f->r = NULL; } } } } void main(){ Init(T); DeleteLev(T,NULL,true); }
-
删除二叉树节点(递归实现)
2022-01-03 20:31:24删除二叉树节点(递归实现)定义删除树节点方法
- 因为二叉树是单向的,所以要判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点.
- 如果当前结点的左子结点不为空,并且左子结点 就是要删除结点,就将this.left = null; 并且就返回(结束递归删除)
- 如果当前结点的右子结点不为空,并且右子结点 就是要删除结点,就将this.right= null ;并且就返回(结束递归删除)
- 如果第2和第3步没有删除结点,就需要向左子树进行递归删除
- 如果第4步也没有删除结点,则应当向右子树进行递归删除.
//递归删除结点 //1.如果删除的节点是叶子节点,则删除该节点 //2.如果删除的节点是非叶子节点,则删除该子树 public void delNode(int no) { //2. 如果当前结点的左子结点不为空,并且左子结点 就是要删除结点,就将this.left = null; 并且就返回(结束递归删除) if(this.left != null && this.left.no == no) { this.left = null; return; } //3.如果当前结点的右子结点不为空,并且右子结点 就是要删除结点,就将this.right= null ;并且就返回(结束递归删除) if(this.right != null && this.right.no == no) { this.right = null; return; } //4.我们就需要向左子树进行递归删除 if(this.left != null) { this.left.delNode(no); } //5.则应当向右子树进行递归删除 if(this.right != null) { this.right.delNode(no); } }
定义二叉树中的删除结点方法
public void delNode(int no) { if(root != null) { //如果只有一个root结点, 这里立即判断root是不是就是要删除结点 if(root.getNo() == no) { root = null; } else { //递归删除 root.delNode(no); } }else{ System.out.println("空树,不能删除~"); } }
-
二叉树删除节点(思路+代码实现)
2022-01-02 21:25:251.删除的节点是叶子节点 2.删除的节点只有一个子树 3.删除的节点有两个子树 删除的节点是叶子节点 找到删除的叶子结点tNode 找到目标节点的父节点pNode(考虑是否有父节点) 找到删除节点是父节点的左子树还是...二叉树的删除要考虑三种情况
1.删除的节点是叶子节点
2.删除的节点只有一个子树
3.删除的节点有两个子树
删除的节点是叶子节点
- 找到删除的叶子结点tNode
- 找到目标节点的父节点pNode(考虑是否有父节点)
- 找到删除节点是父节点的左子树还是右子树
- 根据前边情况进行删除
- 右子树:p.rc=null
- 左子树:p.lc=null
删除的节点只有一个子树
- 找到删除的叶子结点tNode
- 找到目标节点的父节点pNode(考虑是否有父节点)
- 找到删除节点是父节点的左子树还是右子树
- 确定删除节点是左子树还是右子树
- 根据前边情况进行删除
- tNode是它父节点的左子树
- tNode有左子树 : pNode.lc=tNode.lc
- tNode有右子树 : pNode.lc=tNode.rc
- tNode是是它父节点的右子树
- tNode有左子树 : pNode.rc=tNode.lc
- tNode有右子树 : pNode.rc=tNode.rc
- tNode是它父节点的左子树
删除的节点有两个子树
- 找到删除的叶子结点tNode
- 找到目标节点的父节点pNode(考虑是否有父节点)
- 找到删除节点右子树中最小的或找到左子树中最大的
- 将右子树当中最大的值替换掉删除节点的值
- 使删除叶子节点的逻辑,删除最小值
代码实现
/** * 找到删除节点 * @param node 树 * @param value 删除节点值 * @return */ public TreeNode scNode(TreeNode node, int value) { if (root == null) { return null; } // 判断node当前所指的节点是不是删除节点 if (node.value == value) { return node; } else if (value < node.value) { if(node.lc==null) { return null; } return ss(node.lc, value); } else { if(node.rc==null) { return null; } return ss(node.rc, value); } } /** * 找到删除节点父节点 * @param node * @param value 删除节点值 * @return */ public TreeNode scpNode(TreeNode node, int value) { if (root == null) { return null; } if((node.lc!=null&&node.lc.value==value)||(node.rc!=null&&node.rc.value==value)) { return node; }else { if(node.lc!=null&&value<node.value) { return sp(node.lc, value); }else if(node.rc!=null&&value>node.value) { return sp(node.rc, value); }else { return null; } } } //找到右子树最小值 public int rMin(TreeNode node) { TreeNode Node = node; while (Node.lc != null) { Node = Node.lc; } del(root, Node.value);//将右子树最小值节点删除 return Node.value;//最小值 } public void del(TreeNode node, int value) { if (node == null) { return; } TreeNode tNode = ss(node, value); if (tNode == null) { System.out.println("没有删除的节点"); return; } // 整个树只有一个节点 if (node.lc == null && node.rc == null) { root = null; return; } TreeNode pNode = sp(node, value); // 删除点是叶子节点 if (tNode.rc == null && tNode.lc == null) { if (pNode.lc != null && pNode.lc.value == tNode.value) { pNode.lc = null; } else if (pNode.rc != null && pNode.rc.value == tNode.value) { pNode.rc = null; } } else if (tNode.rc != null && tNode.lc != null) { // 删除节点有两个子树节点 int minValue = rMin(tNode.rc); tNode.value = minValue; } else {// 删除节点只有一个子树节点 //删除节点有左子树 if (tNode.lc != null) { // 删除节点点是他父节点的左子树 if (pNode.lc.value == tNode.value) { pNode.lc = tNode.lc; } else {// 删除节点点是他父节点的右子树 pNode.rc = tNode.lc; } } else {//删除节点有右子树 if (pNode.lc.value == tNode.value) {// 删除节点点是他父节点的左子树 pNode.lc = tNode.rc; } else { // 删除节点点是他父节点的右子树 pNode.rc = tNode.rc; } } } } }
-
leetcode 450. 删除二叉搜索树中的节点【BST】
2020-03-24 23:33:58被删除节点为叶子节点,此时只需要直接删除即可; 被删除节点含有一个子节点,此时可以将该节点的子节点替换掉该节点,即将子节点的引用赋值给被删除节点的父节点; 被删除节点含有左子树和右子树,此时可以利用左... -
java中负数的源码反码补码-interviews:CS面试学习表
2021-06-18 22:03:07java中负数的源码反码面试学习表 我用作复习的快速学习表 :grinning_face_with_smiling_eyes: 此外,除了这些简单的主题之外,计算机科学还有更多内容! 有大量在线资源可以拓宽和深化您的核心 CS 知识; 就是这样一... -
leetcode 练习(二叉树删除结点)
2019-08-01 17:36:13给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。 一般来说,删除节点可分为两个步骤: 首先找到... -
AVL树的分析
2020-12-22 16:34:22假如我们要在AVL树中插入或者删除一个节点的话那么就有可能会影响平衡所以就有了旋转的概念,这里假设结点X是失衡点,它必须重新恢复平衡 旋转分为四种: 在结点X的左孩子结点的左子树中插入元素 -
树型算法题解
2020-03-26 17:32:33需要注意一个特殊的情况,如果某个节点只有左节点或者只有右节点,应该统计有节点的那条路径,没有节点的那路径相当于没有叶子节点,不能用那个路径统计。 public class Solution { public int run(TreeNode root) {... -
公共基础数据结构与算法(一)
2020-03-20 17:03:571、对长度为n的线性表排序...2、栈:按照“先进后出”或“后进先出”的原则组织数据(出栈与进栈顺序相反),队列是先进先出,只能在栈顶这一端插入和删除数据(栈顶元素最先被删除;当栈中只剩下栈底一个元素时,栈... -
剑指Offer上的二叉树题目(非基础遍历)
2021-08-18 00:06:59//计算从根节点到当前节点的汇总值 if(cur.left==null&&cur.right==null){//到达叶子节点了 if(sum==target){//从根节点到叶子节点的值等于目标 getList(cur);//获取根节点到此叶子节点的路径 } }else{ if(cur.... -
5.17 位运算 滑动窗口(一) 删除二叉搜索树中节点(重要 450)
2020-05-17 17:32:09#对乘法两部分因子取模 return (part1*part2)%base 450 删除二叉搜索树中节点 用前序节点和后继节点值取代有子树的根节点,然后递归删除叶子结点 # Definition for a binary tree node. # class TreeNode: # def __... -
【Java---数据结构】二叉树(实践篇)
2022-03-02 14:18:42简单说明: 这篇文章的内容是建立在了解二叉树...二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方式有二叉和三叉表示方式。 二叉:孩子表示法 三叉:孩子双亲表示法 // 孩子表示法 class Node { . -
趣店2018秋招笔试题目
2020-12-30 16:00:26看了这么多面经,对自己很有帮助,希望牛客网越做越好,帮助更多... B树的所有关键码都存储在叶子节点上D. B树适用于随机检索,又适用于顺序检索2、Linux的运行级别定义在哪个文件中( A)A. /ect/inittabB. /ect/pro... -
经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】
2021-06-24 18:02:58本文的图片来源网络,仅用于大家学习,侵权联系删除!(下同) 完整代码: package com.keafmd.Sequence; /** * Keafmd * * @ClassName: BubbleSort * @Description: 冒泡排序 * @author: 牛哄哄的柯南 * @date: ... -
ML01决策树
2021-05-03 23:02:21title: 决策树—机器学习经典算法 date: 2021-04-10 tags: ML 基础 categories: dataAnalysis typora-copy-images-to: ./img typora-root-url: ./img ...1)如何从数据表中找出最佳节点和最佳分枝。2)如. -
实战篇3:一切皆对象,文件目录体系(节点树)
2022-03-30 17:40:12AOS与阿里名称冲突,现改为...许多内核对象,如内存对象、CPU对象、IPC对象、线程对象、等等,是没有文件i节点的。c语言功能也强大,但个人认为、想用好并不容易;这段时间,看了不少嵌入式操作系统及相关的源代码;给 -
数据结构之树与二叉树
2022-06-14 13:46:41节点祖先:从根到该节点所经分支上的所有节点,除了此节点本身,其余节点均为此节点的祖先节点,(儿子->父亲->父亲的父亲->…->根) 子孙节点:以该节点为根的子树中的任一节点均为该节点的子孙节点 结点的层次:从... -
[数据结构与算法-16]哈夫曼树和哈夫曼编码
2020-04-16 23:14:14文章目录1、先掌握几个概念1.1 什么是路径?... 先听一遍哈夫曼树的概念:给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(WPL)达到最小,称这样的二叉树为最优二叉树,也成为哈夫曼树(Huf... -
JAVA基础——第十三章 List、Set、数据结构、Collections
2020-08-25 09:36:04任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同 红黑树的特点: 速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于二倍 第二章 List集合 我们掌握了Collection接口的使用后,再来看看Collection... -
mysql面试汇总
2017-09-19 10:11:46数据库优化 建表优化 ...l 第一范式(1NF):强调的是列的原子性,即列不能够再分成其他几列。...l 第二范式(2NF):首先是 1NF...l 没有键值相等的节点(因此,插入的时候一定是叶子节点)。 删除算法... -
107.leetcode题目讲解(C++):二叉树的层次遍历 II
2019-07-16 22:37:41(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历) 例如: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其自底向上的层次遍历为: [ [15,7], [9,20], [3] ] 来源:力扣... -
LeetCode精选题之树
2020-05-22 20:24:20文章目录LeetCode精选题之树递归解题1 二叉树的最大深度--LeetCode1042 平衡...-LeetCode437**8 另一个数的子树--LeetCode5729 对称二叉树--LeetCode10110 二叉树的最小深度--LeetCode11111 左叶子之和--LeetCode4041 -
二叉树的其他题集
2021-04-20 14:25:031,翻转二叉树 来源:226. 翻转二叉树 && 剑指 Offer 27. 二叉树的镜像 思路:交换左右子树,再递归 class Solution { public: TreeNode* mirrorTree... 11,删除给定值的所有叶子节点 来源:1325. 删除给定值的... -
每日一面 - mysql中,innodb表里,某一条数据删除了之后,这条数据会被真实的擦掉吗,还是删除了关系?
2021-01-08 08:42:17删除一条记录,数据原有的被废弃,记录头发生变化,主要是打上了删除标记。也就是原有的数据 deleted_flag 变成 1,代表数据被删除。但是数据没有被清空,在新一行数据大小小于这一行的时候,可能会占用这一行。这样... -
数据结构期末复习
2020-09-04 20:12:57宜采用的存储结构为用尾指针表示的循环单链表 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是O(N),因为要想使插入的元素后仍然有序,就是把所有节点(n个节点)都遍历下,所以是N。... -
(剑指OFFER面试题34)二叉树中和为某一值的路径
2018-06-24 16:58:55路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 例如下图,输入的二叉树和整数22,则打印出两条路径,第一条路径包含节点10、12;第二条路径包含节点10、5和7 。 一般的数据结构和算法... -
数据结构试卷及答案(七)
2018-08-20 07:25:31一、选择题1、设某无向图有n个顶点,则该无向图的邻接表中有( )个表头结点。(A) 2n(B) n(C) n/2(D) n(n-1)参考答案是:B2、设无向图G中有n个顶点,则该无向图的最小生成树上有( )条边。(A) n(B) n-1(C) 2n(D) 2n... -
NOIP2009年普及组初赛试题答案及解析
2020-10-27 13:37:08它的叶结点数目最多为:(D) A) 2n + 1 B) 2n-1 C) n-1 D) n+1 【解析】 根据二叉树的性质3:对于任何一棵二叉树,如果其叶结点数为N0(N0表示度为0的点也就是叶子结点),而度为2的结点为N2,则N0=N2+1。... -
哈夫曼树
2013-08-21 16:58:01哈夫曼树定义为:给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree)。 1、那么什么是权值?什么是路径长度?什么是带权路径长度呢?...
收藏数
3,849
精华内容
1,539