首页 > 其他分享 >【二叉树】删点成林

【二叉树】删点成林

时间:2022-10-24 19:33:03浏览次数:85  
标签:right TreeNode 成林 nil val 二叉树 删点 root left


0x00 题目

给出二叉树的根节点 ​​root​​​ 树上每个节点都有一个不同的值
如果节点值在 ​​to_delete​​ 中出现
我们就把该节点从树上​​删去​​ 最后得到一个森林(一些不相交的树构成的集合)

返回森林中的每棵树
你可以按任意顺序组织答案


0x01 思路

某个节点需要​​删除​​​时
需要判断它的​​​左右​​​节点是否为​​空​​​ 不为空则​​添加​​到结果数组中
然后返回一个​​空节点​​(nil) 给上层
上层直接替换即可
所以,按照这个思路
使用​​后序​​遍历方式即可


0x02 解法

语言:​​Swift​

树节点:​​TreeNode​

public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init() { self.val = 0; self.left = nil; self.right = nil; }
public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
}

解法:

func delNodes(_ root: TreeNode?, _ to_delete: [Int]) -> [TreeNode?] {
var res: [TreeNode?] = []

func del(_ root: TreeNode?, _ to_delete: [Int]) -> TreeNode? {
guard let root = root else { return nil }

// 分别去左右子树进行删除操作
let left = del(root.left, to_delete)
let right = del(root.right, to_delete)

// 更新左右子树
root.left = left
root.right = right

// 节点需要删除
if to_delete.contains(root.val) {
if left != nil {
res.append(left)
}
if right != nil {
res.append(right)
}
return nil
}

return root
}

// 根节点是否需要删除?
let r = del(root, to_delete)
if r != nil {
res.append(r)
}

return res
}

0x03 我的小作品

欢迎体验我的作品之一:​​小编辑器-XCompiler​​​ 在线编辑器,包含多种语言
​App Store​​ 搜索即可~



标签:right,TreeNode,成林,nil,val,二叉树,删点,root,left
From: https://blog.51cto.com/u_15844020/5791041

相关文章

  • 【二叉树】二叉树中的最长交错路径
    0x00题目给你一棵以​​root​​为根的二叉树,二叉树中的交错路径定义如下:选择二叉树中​​任意​​​节点和一个方向(​​左​​​或者​​右​​​)如果前进方向为​​......
  • 【二叉树】最大层内元素和
    0x00题目给你一个二叉树的根节点​​root​​​设根节点位于二叉树的第​​1​​层而根节点的子节点位于第​​2​​层依此类推请返回层内元素之和​​​最大​​......
  • 数据结构---二叉树
    二叉树的结构体:左右子树指针(Tree*) 值(int)typedefstructTree{chardata;structTree*lchild,*rchild;}*BiTree;二叉树的先序创建BiTreeCreate(......
  • 2022.10.20-C 二叉树
    题意有一颗二叉树,满足一个结点要么是叶子结点,要么有两个儿子。同时,不存在一个叶子结点,使得它到根的路径上经过了\(\gem\)条向左的边。(左右子树有区别)对于\(1\lek\l......
  • 数据结构【C语言版】二叉树的结构和遍历的实现
    数据结构【C语言版】二叉树的结构和遍历的实现1.二叉树的存储结构二叉树一般分为两种存储结构,一种是顺序结构,一种是链表结构。顺序结构顺序结构存储就是使用数组来......
  • Madoka and the Sixth-graders (全排列队列,每一个点可以向外连1条线题型+倍增法处理
    题意:Madoka的教室里有 nn 个座位,一开始,编号为 ii 的座位上坐着编号为 b_i(1\leb_i\len)bi​(1≤bi​≤n) 的同学。门外有排成一队的,编号从 n+1n+1 开始的,......
  • 二叉树的右视图
    给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 publicList<Integer>rightSideView(TreeNoderoot){......
  • 【算法】算法题目三道模拟计算器,设计学生类和子类,二叉树开为链表
    算法题目描述算法知识点如下:模拟计算器,类型:算法初阶,比较简单。设计学生类和子类,类型:基础知识,比较简单。二叉树开展为链表,类型:栈,树,中等难度。第一题算法题目描述模拟简单的......
  • 算法与数据结构——二叉树遍历应用
    题目:  代码:#include<iostream>#include<stdlib.h>usingnamespacestd;typedefstructTreeNode{chardata;structTreeNode*lchild;struct......
  • 二叉树部分知识点
    关于满二叉树和完全二叉树:满二叉树:每个分支节点都存在左子树和右子树,且叶子节点在同一层完全二叉树:按层序编号,如果编号出现空档,则说明不是完全二叉树,反之则是 已知前......