当前位置： 首页 > article >正文

前端算法：树（力扣144、94、145、100、104题）

article 2024/11/20 0:39:46

目录

一、树（Tree）

1.介绍

2.特点

3.基本术语

4.种类

二、树之操作

1.遍历

前序遍历（Pre-order Traversal）：访问根节点 -> 遍历左子树 -> 遍历右子树。

中序遍历（In-order Traversal）：遍历左子树 -> 访问根节点 -> 遍历右子树（用于 BST 时可得到排序结果）。

后序遍历（Post-order Traversal）：遍历左子树 -> 遍历右子树 -> 访问根节点。

层序遍历（Level-order Traversal）：逐层访问树的节点，通常使用队列实现。

2.插入和删除

3.查找

三、树的力扣算法实战

1.144. 二叉树的前序遍历

2.94. 二叉树的中序遍历

 3.145. 二叉树的后序遍历

4.100. 相同的树

5.104. 二叉树的最大深度

一、树（Tree）

1.介绍

树（Tree）是一种重要的数据结构，广泛应用于计算机科学中。它由节点组成，并且有一个根节点，其他节点通过边连接形成层级关系。

2.特点

  1. 层级关系：树结构是分层的，根节点位于顶层，每个节点可以有多个子节点。
  2. 无环性：树中不存在环，即从一个节点出发不可能回到该节点。
  3. 节点的子节点：每个节点可以有零个或多个子节点。

3.基本术语

  • 根节点：树的顶层节点。
  • 叶子节点：没有子节点的节点。
  • 子节点：某个节点直接连接的下层节点。
  • 兄弟节点：同一父节点的子节点。
  • 高度：树的高度是从根节点到最深叶子节点的最长路径的边数。

4.种类

  1. 树（Tree）：一般的树结构，没有特定的限制。

  2. 二叉树（Binary Tree）：每个节点最多有两个子节点。

    • 完全二叉树（Complete Binary Tree）：除了最后一层外，其他层的节点都填满，最后一层的节点尽量向左排列。
    • 满二叉树（Full Binary Tree）：每个节点要么是叶子节点，要么有两个子节点。
    • 非完全二叉树（Incomplete Binary Tree）：不是完全二叉树的任意形式。

  3. 二叉搜索树（Binary Search Tree, BST）：一种特殊的二叉树，左子树的所有节点值小于根节点，右子树的所有节点值大于根节点。

  4. 自平衡树（Self-balancing Tree）：如 AVL 树和红黑树，保持树的高度平衡以优化查找效率。

  5. N 叉树（N-ary Tree）：每个节点可以有 N 个子节点的树结构。

  6. Trie（前缀树）：一种用于存储字符串的树，常用于快速查找和前缀匹配。

二、树之操作

1.遍历

前序遍历（Pre-order Traversal）：访问根节点 -> 遍历左子树 -> 遍历右子树。
    // 前序遍历
    preOrderTraversal(node) {
        if (node) {
            console.log(node.value);
            this.preOrderTraversal(node.left);
            this.preOrderTraversal(node.right);
        }
    }
中序遍历（In-order Traversal）：遍历左子树 -> 访问根节点 -> 遍历右子树（用于 BST 时可得到排序结果）。
    // 中序遍历
    inOrderTraversal(node) {
        if (node) {
            this.inOrderTraversal(node.left);
            console.log(node.value);
            this.inOrderTraversal(node.right);
        }
    }
后序遍历（Post-order Traversal）：遍历左子树 -> 遍历右子树 -> 访问根节点。

    // 后序遍历
    postOrderTraversal(node) {
        if (node) {
            this.postOrderTraversal(node.left);
            this.postOrderTraversal(node.right);
            console.log(node.value);
        }
    }
层序遍历（Level-order Traversal）：逐层访问树的节点，通常使用队列实现。
    // 层序遍历
    levelOrderTraversal() {
        if (!this.root) return;

        const queue = [this.root];
        while (queue.length > 0) {
            const node = queue.shift();
            console.log(node.value);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }

2.插入和删除

插入：在二叉搜索树中，插入新节点时需要找到合适的位置，保证 BST 的性质。

    // 插入
    insert(value) {
        const newNode = new TreeNode(value);
        if (this.root === null) {
            this.root = newNode;
            return;
        }
        this.insertNode(this.root, newNode);
    }

    insertNode(node, newNode) {
        if (newNode.value < node.value) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }

删除：删除节点时可能需要重新调整树结构，以保持树的性质，尤其在 BST 中。

    // 删除
    delete(value) {
        this.root = this.deleteNode(this.root, value);
    }

    deleteNode(node, value) {
        if (node === null) {
            return null;
        }
        if (value < node.value) {
            node.left = this.deleteNode(node.left, value);
        } else if (value > node.value) {
            node.right = this.deleteNode(node.right, value);
        } else {
            // 找到要删除的节点
            if (node.left === null && node.right === null) {
                return null; // 无子节点
            }
            if (node.left === null) {
                return node.right; // 只有右子节点
            }
            if (node.right === null) {
                return node.left; // 只有左子节点
            }
            // 找到右子树中的最小节点
            const minNode = this.findMinNode(node.right);
            node.value = minNode.value; // 替换值
            node.right = this.deleteNode(node.right, minNode.value); // 删除最小节点
        }
        return node;
    }

3.查找

在树中查找节点的过程依赖于树的性质。对于二叉搜索树，可以通过比较节点值快速找到目标节点。

    search(value) {
        return this.searchNode(this.root, value);
    }

    searchNode(node, value) {
        if (node === null) {
            return false;
        }
        if (value === node.value) {
            return true;
        }
        return value < node.value
            ? this.searchNode(node.left, value)
            : this.searchNode(node.right, value);
    }

三、树的力扣算法实战

1.144. 二叉树的前序遍历

题目描述：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]

输出：[1,2,3]

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[1,2,4,5,6,7,3,8,9]

示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

解题思路：将二叉树进行先序遍历（中左右：根节点->左子树->右子树）

代码：

var preorderTraversal = function(root) {
    const arr = []

    const fun = (node) =>{
        if(node){
            arr.push(node.val)
                fun(node.left)
                fun(node.right)
        }
        
    }

    fun(root)
    return arr
};

2.94. 二叉树的中序遍历

题目描述：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

解题思路：将二叉树进行中序遍历（左中右：左子树->根节点->右子树）

代码：

var inorderTraversal = function(root) {
    const arr = []
    const fun = (root) =>{
        if(!root) return
        fun(root.left)
        arr.push(root.val)
        fun(root.right)
    }
    fun(root)
    return arr
};

 3.145. 二叉树的后序遍历

题目描述：给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]

输出：[3,2,1]

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[4,6,7,5,2,9,8,3,1]

示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

解题思路：将二叉树进行中序遍历（左右中：左子树->右子树->根节点）

代码：

var postorderTraversal = function(root) {
    const arr = []
    const fun = (root) =>{
        if(!root) return
        fun(root.left)
        fun(root.right)
        arr.push(root.val)
    }
    fun(root)
    return arr
};

4.100. 相同的树

题目描述：

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

 解题思路：首先判断两个节点是否都为空，是则返回true;如果一个为空一个不为空，则返回false，再判断两个节点的val值是否相同，不同返回false，依次进行传入两棵树的左节点和右节点

代码：

var isSameTree = function(p, q) {
    if(p === null && q === null) return true;
    if(p === null || q === null) return false
    if(p.val !== q.val) return false
    return isSameTree(p.left,q.left) && isSameTree(p.right,q.right)
};

5.104. 二叉树的最大深度

题目描述：

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

解题思路： 首先判断树是否为空，空则返回0，将树放入栈中，以栈的长度为值进行遍历，将栈的长度定义一个值len，每循环一次计数器num+1，len--，依次弹出stack的栈中元素，判断是否有左右子节点，在将其压入栈中，最后返回num值

代码

var maxDepth = function(root) {
    if(!root) return 0
    const stack = [root]
    let num = 0
    while(stack.length){
        let len = stack.length
        num++
        while(len--){
            const o = stack.shift()
            o.left && stack.push(o.left)
            o.right && stack.push(o.right)
        }
    }
    return num
};


http://www.kler.cn/a/400804.html

相关文章：

  • 为何数据库推荐将IPv4地址存储为32位整数而非字符串？
  • 内网安全隧道搭建-ngrok-frp-nps-sapp
  • 使用nossl模式连接MySQL数据库详解
  • Oracle OCP认证考试考点详解082系列19
  • 【不写for循环】玩玩行列
  • 【.NET 8 实战--孢子记账--从单体到微服务】--简易权限--完善TODO标记的代码
  • Linux配置yum源练习
  • 学习笔记029——Ubuntu安装Nginx
  • 机器学习——期末复习 重点题归纳
  • 学习笔记022——Ubuntu 安装 MySQL8.0版本踩坑记录
  • 8、watch数据监视
  • Vscode离线安装插件的方法
  • ed by: java.lang.NoClassDefFoundError: android
  • 【redis】—— 环境搭建教程
  • CSS基础知识04
  • [C++]：C++11(一)
  • 基于Java的校园便利平台
  • elasticsearch是如何实现master选举的？
  • Matlab信号处理：短时傅里叶变换
  • Spring Boot汽车世界：资讯与技术的交汇
  • vue路由的钩子函数?
  • 离散数学与数据结构是什么关系
  • SLM561A系列60V10-50mA单通道线性恒流LED驱动芯片，为汽车照明、景观照明助力
  • 力扣2298. 周末任务计数
  • Linux系统-redis集群、nacos、nginx、keepalived、mysql开机自启
  • RabbitMQ教程：发布/订阅模式（Publish/Subscribe）（三）