【数据结构与算法】二叉树遍历、判断和 diff 算法

image.png

遍历

深度优先遍历

function Node(value) {
    this.value = value
    this.left = null
    this.right = null
}

let a  = new Node('a')
let b  = new Node('b')
let c  = new Node('c')
let d  = new Node('d')
let e  = new Node('e')
let f  = new Node('f')
let g  = new Node('g')
a.left = c
a.right = b
c.left = f
c.right= g
b.left = d
b.rihgt = e

function deepSearch(root, target) {
    if (root == null) return false
    if (root.value == target) return true
    let left = deepSearch(root.left,target)
    let right = deepSearch(root.right,target)
    return left || right
}

console.log(deepSearch(a, 'c'))

广度优先遍历

function Node(value) {
    this.value = value
    this.left = null
    this.right = null
}

let a = new Node('a')
let b = new Node('b')
let c = new Node('c')
let d = new Node('d')
let e = new Node('e')
let f = new Node('f')
let g = new Node('g')
a.left = c
a.right = b
c.left = f
c.right = g
b.left = d
b.rihgt = e

function breadthSearch(rootList, target) {
    if (rootList == null || rootList.length == 0) return false
    // 当前层的所有子节点
    let childList = []
    for (let i = 0; i < rootList.length; i++) {
        if (rootList[i] != null && rootList[i].value == target) {
            return true
        } else {
            rootList[i].left && childList.push(rootList[i].left)
            rootList[i].right && childList.push(rootList[i].right)
        }
    }
    return breadthSearch(childList, target)
}

console.log(breadthSearch([a], 'n'))

判断是否相同

普通情况

function Node(value) {
    this.value = value
    this.left = null
    this.right = null
}

let a1 = new Node('a')
let b1 = new Node('b')
let c1 = new Node('c')
let d1 = new Node('d')
let e1 = new Node('e')
let f1 = new Node('f')
let g1 = new Node('g')
a1.left = c1
a1.right = b1
// c1.left = f1
c1.right = g1
b1.left = d1
b1.right = e1
let a2 = new Node('a')
let b2 = new Node('b')
let c2 = new Node('c')
let d2 = new Node('d')
let e2 = new Node('e')
let f2 = new Node('f')
let g2 = new Node('g')
a2.left = c2
a2.right = b2
// c2.left = f2
c2.right = g2
b2.left = d2
b2.right = e2

function compareTree(root1, root2) {
    if (root1 == null && root2 == null) return true
    if (root1 == null || root2 == null) return false
    let leftTree = compareTree(root1.left, root2.left)
    let rightTree = compareTree(root1.right, root2.right)
    return root1.value == root2.value && leftTree && rightTree
}

console.log(compareTree(a1, a2))

特殊情况

子树左右互换也算相同。

function Node(value) {
    this.value = value
    this.left = null
    this.right = null
}

let a1 = new Node('a')
let b1 = new Node('b')
let c1 = new Node('c')
let d1 = new Node('d')
let e1 = new Node('e')
let f1 = new Node('f')
let g1 = new Node('g')
a1.left = c1
a1.right = b1
c1.left = f1
c1.right = g1
b1.left = d1
b1.right = e1
let a2 = new Node('a')
let b2 = new Node('b')
let c2 = new Node('c')
let d2 = new Node('d')
let e2 = new Node('e')
let f2 = new Node('f')
let g2 = new Node('g')
a2.left = b2
a2.right = c2
c2.left = f2
c2.right = g2
b2.left = d2
b2.right = e2

function compareTree(root1, root2) {
    if (root1 == null && root2 == null) return true
    if (root1 == null || root2 == null) return false
    return root1.value == root2.value && compareTree(root1.left, root2.left) && compareTree(root1.right, root2.right)
    || root1.value == root2.value && compareTree(root1.left, root2.right) && compareTree(root1.right, root2.left)
}

console.log(compareTree(a1, a2))

diff 算法

function Node(value) {
    this.value = value
    this.left = null
    this.right = null
}

let a1 = new Node('a')
let b1 = new Node('b')
let c1 = new Node('c')
let d1 = new Node('d')
let e1 = new Node('e')
let f1 = new Node('f')
let g1 = new Node('g')
a1.left = c1
a1.right = b1
c1.left = f1
c1.right = g1
b1.left = d1
b1.right = e1
let a2 = new Node('a')
let b2 = new Node('z')
let c2 = new Node('c')
let d2 = new Node('x')
let e2 = new Node('e')
let f2 = new Node('f')
let g2 = new Node('g')
a2.left = c2
a2.right = b2
c2.left = f2
// c2.right = g2
f2.right = g2
b2.left = d2
b2.right = e2

function diffTree(root1, root2, diffList) {
    if (root1 == null && root2 == null) {
        return diffList
    } else if (root1 == null && root2 != null) {
        diffList.push({type: '新增', origin: null, now: root2});
    } else if (root1 != null && root2 == null) {
        diffList.push({type: '删除', origin: root1, now: null});
    } else if (root1.value != root2.value) {
        diffList.push({type: '修改', origin: root1, now: root2});
        // 判断父节点本身改变,但是子节点并没有改变的情况
        diffTree(root1.left, root2.left, diffList)
        diffTree(root1.right, root2.right, diffList)
    } else {
        diffTree(root1.left, root2.left, diffList)
        diffTree(root1.right, root2.right, diffList)
    }
}
/**
 * 判断树的变化
 * {type: '新增', origin: null, now: c2}
 * {type: '修改', origin: c1, now: c2}
 * {type: '删除', origin: c2, now: null}
 * @type {*[]}
 */
let diffList = []
diffTree(a1, a2, diffList)
console.log(diffList)

image.png

image.png

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/505577.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

如何提升公众号搜索量?分享内部运营的5步优化技术!

最近一直有自媒体同行朋友在写关于公众号的内容&#xff0c;很多都说公众号现在没得玩了。其实&#xff0c;在运营自媒体上面&#xff0c;思维不通&#xff0c;技术不到位&#xff0c;哪个平台都不适合你玩。 想要在自媒体上面运营变现&#xff0c;一定不要先点击广告变现&…

【二分查找】查找数列中数第一次出现的编号

一道巩固二分查找知识的题&#xff0c;非常简单&#xff0c;一起做一下吧 题目&#xff1a; 答案&#xff1a; #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N1000010;int n,m; int q[N];bool isBlue(int num…

7种2024年算法优化BP,实现回归,单/多变量输入,单/多步预测功能,机器学习预测全家桶再更新!...

截止到本期MATLAB机器学习预测全家桶&#xff0c;一共发了19篇关于机器学习预测代码的文章。算上这一篇&#xff0c;一共20篇&#xff01;参考文章如下&#xff1a; 1.五花八门的机器学习预测&#xff1f;一篇搞定不行吗&#xff1f; 2.机器学习预测全家桶&#xff0c;多步预测…

中文乱码 一文讲解 字符集和字符编码 不再困惑(有源码)

初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github&#xff1a;codetoys&#xff0c;所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的&#xff0c;可以在任何平台上使用。 这可能是应用级程序员最困惑的…

SSTI 服务器端模板注入(Server-Side Template Injection)

1.Web_python_template_injection {{}}是变量包裹标识符&#xff0c;里面存放的是一个变量&#xff0c;当你输入 http://61.147.171.105:55121/{{8*8}} 执行成功&#xff0c;说明存在模版注入。接下来&#xff0c;开始想办法编代码拿到服务器的控制台权限 。 首先&#xff0c…

Redis 命令行客户端

目 录 redis 客户端介绍 redis 客户端介绍 redis 是一个 客户端-服务器 结构的程序&#xff01;&#xff01;&#xff08;类似于 MySQL&#xff09; 因此 redis 客户端和服务器 可以在同一个主机上&#xff0c;也可以在不同主机上. Redis 的客户端也有很多种形态&#xff1a;…

2024 批量下载吾爱破解公众号文章内容/话题/图片/封面/视频/音频,导出文章pdf合集,excel数据包含阅读数留言数粉丝数

前几天看到吾爱破解论坛公众号文章吾爱破解精华集2023&#xff0c;于是把吾爱破解论坛公众号2022-2023年所有公众号文章也下载做成合集分享给大家&#xff0c;网盘地址https://pan.quark.cn/s/9c1b60b822a7 下载的excel文章数据包含文章日期&#xff0c;文章标题&#xff0c;文…

基于springboot实现图书个性化推荐系统项目【项目源码+论文说明】

基于springboot实现图书个性化推荐系统演示 摘要 本论文主要论述了如何使用JAVA语言开发一个图书个性化推荐系统&#xff0c;本系统将严格按照软件开发流程进行各个阶段的工作&#xff0c;采用B/S架构&#xff0c;面向对象编程思想进行项目开发。在引言中&#xff0c;作者将论…

risc-v向量扩展strlen方法学习

riscv向量文档中给出了strlen的实现&#xff0c; 大概是这么一个思路&#xff0c; 加载向量: 使用向量加载指令&#xff08;如 vload&#xff09;从内存中加载一个向量长度的字符。比较向量与零: 使用向量比较指令&#xff08;如 vmask 或 vcmpeq&#xff09;来检查向量中的每…

Js之运算符与表达式

运算符&#xff1a;也叫操作符&#xff0c;是一种符号。通过运算符可以对一个或多个值进行运算&#xff0c;并获取运算结果。 表达式&#xff1a;由数字、运算符、变量的组合&#xff08;组成的式子&#xff09;。 表达式最终都会有一个运算结果&#xff0c;我们将这个结果称…

【电路笔记】-快速了解数字逻辑门

快速了解数字逻辑门 文章目录 快速了解数字逻辑门1、概述2、集成电路的分类3、摩尔定律4、数字逻辑状态5、数字逻辑噪声6、简单的基本数字逻辑门7、基本 TTL 逻辑门8、发射极耦合数字逻辑门9、集成电路的“74”子族10、基本 CMOS 数字逻辑门数字逻辑门是一种电子电路,它根据其…

C++从入门到精通——引用()

C的引用 前言一、C引用概念二、引用特性交换指针引用 三、常引用保证值不变权限的方法权限的放大权限的缩小权限的平移类型转换临时变量 四、引用的使用场景1. 做参数2. 做返回值 五、传值、传引用效率比较值和引用的作为返回值类型的性能比较 六、引用和指针的区别引用和指针的…

动态规划-最长回文子串

动态规划-最长回文子串 原题描述解答中心移动思想代码实现复杂度分析时间复杂度空间复杂度 动态规划思想代码实现复杂度分析时间复杂度空间复杂度 突然觉得很有必要将学过的内容记录下来&#xff0c;这样后续在需要用到的时候就可以避免从头进行学习&#xff0c;而去看自己之前…

调试技巧安全预编译头文件(C++基础)

调试 调试可以选择条件调试和操作调试&#xff1a; 条件调试来选择条件进入断点设置&#xff0c;操作调试来使达到断点条件后完成某些操作&#xff08;一般是output窗口输出&#xff09;。 在这里就只输出了小于6的条件。 安全 降低崩溃、内存泄露、非法访问等问题。 应该转…

GetSystemTimes:获取CPU占用率(WIN API)

原文链接&#xff1a;https://blog.csdn.net/qq_28742901/article/details/104960653 GetSystemTimes函数&#xff1a; BOOL WINAPI GetSystemTimes(__out_opt LPFILETIME lpIdleTime, // 空闲时间__out_opt LPFILETIME lpKernelTime, // 内核进程占用时间__out_opt LPFILETI…

【JavaWeb】Day29.SpringBootWeb请求响应——请求(二)

请求响应 4.数组集合参数 数组集合参数的使用场景&#xff1a;在HTML的表单中&#xff0c;有一个表单项是支持多选的(复选框)&#xff0c;可以提交选择的多个值。 4.1 数组 数组参数&#xff1a;请求参数名与形参数组名称相同且请求参数为多个&#xff0c;定义数组类型形参即…

C++取经之路(其一)——namespace(命名空间),cout,cin(输入输出流),缺省参数。

目录 目录&#xff1a; 前言&#xff1a; namespace(命名空间): 命名空间可以嵌套使用如&#xff1a; 相同的命名空间 cout cin输入输出 std命名空间的使用惯例&#xff1a; 缺省参数&#xff1a; 缺省类型&#xff1a; 前言&#xff1a; 最近开始学习C了&#xff0c;…

Web 前端性能优化之二:图像优化

1、图像优化 HTTP Archive上的数据显示&#xff0c;网站传输的数据中&#xff0c;60%的资源都是由各种图像文件组成的。 **图像资源优化的根本思想&#xff0c;可以归结为两个字&#xff1a;压缩。**无论是选取何种图像的文件格式&#xff0c;还是针对同一种格式压缩至更小的…

两种序列化的方式:fastjson 和 Jackson

public class TestMain {public static void main(String[] args) throws JsonProcessingException {//创建一个课表对象LearningLesson lesson new LearningLesson();lesson.setId(1L);lesson.setCourseId(2L);lesson.setStatus(LessonStatus.EXPIRED); //课程状态&#xff0…

网安基础2-Sniffer的使用与防范

1. 嗅探器sniffer的工作原理 能捕获经过该网络设备的报文&#xff0c;通过分析网络流量&#xff0c;找出关键信息&#xff0c;解决网络问题。 不同于键盘捕获程序&#xff0c;如keylogger利用中断或钩子技术&#xff0c;Sniffer将网络接口置成适当的模式&#xff0c;如杂收。…