web前端算法简介之树-二叉树

  • • 二叉树 VS 多叉树

      • • 二叉树

      • • 多叉树

    • • 二叉树遍历

      • • 二叉树的前序遍历

      • • 二叉树的中序遍历

      • • 二叉树的后序遍历

    • • 其他算法题

      • • 二叉树的最小深度

      • • 二叉树的最大深度

      • • 翻转二叉树

      • • 相同的树

二叉树 VS 多叉树

二叉树

二叉树(Binary Tree)是一种数据结构,它是由n(n≥0)个节点构成的有限集合。

这个集合或者为空集(即没有任何节点,称为空二叉树),或者由一个根节点以及两个互不相交的子集组成,这两个子集分别称为 左子树(left subtree) 和 右子树(right subtree),每个子集本身也是一棵二叉树。

具体来说:

  1. 1. 根节点:每棵非空二叉树都有且仅有一个被称为“根”的节点。

  2. 2. 子节点:每个节点最多可以有两个子节点,一个是左子节点,另一个是右子节点。

  3. 3. 递归定义:若一棵非空二叉树的根节点存在,则其左子树和右子树都是根据相同规则构造的二叉树。

举例说明:

    5
   / 
  3   7
 /    
2   4   8

上图展示了一棵非空二叉树,其中:

- 节点5是根节点。
- 节点3和节点7分别是节点5的左子节点和右子节点,它们各自又构成了两棵新的二叉树。
- 节点2和节点4是节点3的左、右子节点。
- 节点8是节点7的右子节点,而节点7没有左子节点。

按照二叉树的性质,任意节点的所有后代节点间都不会有交叉关系,即它们要么属于当前节点的左子树,要么属于右子树,不会同时出现在另一侧的子树中。

二叉树例子

const tree = {
    val:'1',
    left:{
        val:'2',
        left:{val:'4',left:null,right:null},
        right:{val:'5',left:null,right:null}
    },
    right:{
        val:'3',
        left:{val:'6',left:null,right:null},
        right:{val:'7',left:null,right:null}
    }
}

多叉树

多叉树(Multiway Tree),又称多分支树或多路树,是一种更为通用的数据结构,每个节点可以有任意数量的子节点。

与二叉树不同,在多叉树中,每个节点可以有超过两个孩子的节点。

具体来说:

  1. 1. 根节点:每棵非空多叉树都有一个被称为“根”的节点。

  2. 2. 子节点:每个节点可以有多个子节点,这些子节点之间没有顺序上的优先级,通常以列表或其他集合形式存储。

举例说明:

    A
   / | 
  B  C  D
 /      
E   F     G
      / 
     H   I

在上图所示的多叉树中:

- 节点A是根节点。
- 节点A有三个子节点B、C和D。
- 节点B有两个子节点E和F。
- 节点C没有子节点。
- 节点D有一个子节点G,而节点G又有两个子节点H和I。

多叉树在很多实际应用中出现,比如文件系统目录结构(一个目录下可以有多个子目录和文件)、组织架构(一个部门下可以有多个子部门或员工)等场景。

二叉树遍历

二叉树的前序遍历

二叉树的前序遍历,也叫根-左-右(Root-Left-Right)遍历,是一种常见的深度优先遍历方式。

它的遍历顺序是 首先访问根节点,然后遍历左子树,最后遍历右子树

具体算法步骤如下:

  1. 1. 访问根节点。

  2. 2. 递归地对左子树进行前序遍历。

  3. 3. 递归地对右子树进行前序遍历。

例如,对于一个二叉树:

    A
   / 
  B   C
 /    
D   E   F

其前序遍历结果为:A -> B -> D -> E -> C -> F

算法题

  1. 1. 二叉树的前序遍历

leetcode地址: https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

示例 1:

web前端算法简介之树-二叉树
输入:root = [1,null,2,3]
输出:[1,2,3]

示例 2:

输入:root = []
输出:[]

示例 3:

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

示例 4:

web前端算法简介之树-二叉树
输入:root = [1,2]
输出:[1,2]

示例 5:

web前端算法简介之树-二叉树
输入:root = [1,null,2]
输出:[1,2]

提示:

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶:递归算法很简单,你可以通过迭代算法完成吗?

js实现方案 — 使用递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNoderoot
 * @return {number[]}
 */

var preorderTraversal = function (root) {
    // 定义一个数组
    let arr = []

    // 定义需要递归的函数
    var fun = (node) => {
        // 如果节点存在
        if (node) {
            // 根节点
            arr.push(node.val)

            // 左子树
            fun(node.left)

            //右子树
            fun(node.right)
        }
    }

    fun(root)
    return arr
};

js实现方案 — 使用栈方式

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNoderoot
 * @return {number[]}
 */

var preorderTraversal = function (root) {
    // 判断根节点
    if (!root) return []

    // 新建一个数组
    let arr = []

    // 根节点入栈
    let stack = [root]

    while (stack.length) {
        // 出栈
        let o = stack.pop()
        arr.push(o.val)

        // push 是往后加,所以,先加右侧
        // {{左},左},{左},{左},{右},{右},{右},{右},{右} }
        // pop 的时候,右侧先出
        o.right && stack.push(o.right)
        o.left && stack.push(o.left)
    } 
    return arr 
};

二叉树的中序遍历

二叉树的中序遍历是指按照“ 左子树-根节点-右子树 ”的顺序遍历二叉树的节点。

具体算法步骤如下:

中序遍历是二叉树遍历的一种方式,其步骤如下:

  1. 1. 先递归遍历左子树。

  2. 2. 访问根节点。

  3. 3. 递归遍历右子树。

如果以节点的值作为输出,中序遍历可以用递归或者迭代的方式实现。

假设有一个二叉树如下所示:

    1
   / 
  2   3
 / 
4   5

按照中序遍历的顺序输出结果为:[4, 2, 5, 1, 3]。

例子

JavaScript中,二叉树的中序遍历同样可以通过递归或迭代方式实现。

以下是两种方法的代码示例:

递归实现

// 定义一个二叉树节点类
class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = (val === undefined ? 0 : val);
        this.left = left;
        this.right = right;
    }
}

// 中序遍历(递归)
function inorderTraversal(root) {
    if (!root) return []; // 如果根节点为空,则返回空数组
    return [
        ...inorderTraversal(root.left), // 首先遍历左子树
        root.val, // 然后访问根节点
        ...inorderTraversal(root.right) // 最后遍历右子树
    ];
}

迭代实现

function inorderTraversal(root) {
    let result = [];
    let stack = [];

    while (root || stack.length > 0) {
        while (root) { // 将所有左孩子压入栈,并将当前节点移到其右孩子
            stack.push(root);
            root = root.left;
        }

        // 弹出栈顶元素并访问节点
        root = stack.pop();
        result.push(root.val);

        // 移动到当前节点的右孩子
        root = root.right;
    }

    return result;
}

以上两种方法都可以正确地按照“左子树-根节点-右子树”的顺序遍历二叉树的所有节点。

算法题

  1. 1. 二叉树的中序遍历

leetcode官网地址:https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

示例 1:

web前端算法简介之树-二叉树
输入:root = [1,null,2,3]
输出:[1,3,2]

示例 2:

输入:root = []
输出:[]

示例 3:

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

提示:

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

js代码实现 –递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNoderoot
 * @return {number[]}
 */

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;
};

js代码实现 –非递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNoderoot
 * @return {number[]}
 */

var inorderTraversal = function (root) {
    // 定义一个数组
    let arr = []

    // 新建一个栈
    let stack = []

    // 存储根节点
    let o = root

    while (stack.length || o) { // 判断栈中是否有内容,以及是否存在根节点
        while (o) {
            stack.push(o)
            o = o.left
        }

        let n = stack.pop()
        arr.push(n.val)
        o = n.right
    }

    return arr
};

二叉树的后序遍历

二叉树的后序遍历(Postorder Traversal)是一种按照“左子树-右子树-根节点”的顺序访问每个节点的方法。

具体步骤如下:

  1. 1. 从根节点开始。

  2. 2. 首先,递归地对根节点的左子树进行后序遍历。

  3. 3. 然后,递归地对根节点的右子树进行后序遍历。

  4. 4. 最后,访问根节点本身。

算法题

  1. 1. 二叉树的后序遍历

leetcode的地址:https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。

示例 1:

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

示例 2:

输入:root = []
输出:[]

示例 3:

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

提示:

树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶:递归算法很简单,你可以通过迭代算法完成吗?

js实现方案–递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNoderoot
 * @return {number[]}
 */

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

s实现方案–非递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNoderoot
 * @return {number[]}
 */

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

    if (!root) return [];
    let arr = [];
    let stack = [root];
    while (stack.length) {
        const o = stack.pop();
        arr.unshift(o.val);
        o.left && stack.push(o.left);
        o.right && stack.push(o.right);
    }
    return arr;
};

其他算法题

二叉树的最小深度

leetcode地址:https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明:叶子节点是指没有子节点的节点。

示例 1:

web前端算法简介之树-二叉树
输入:root = [3,9,20,null,null,15,7]
输出:2

示例 2:

输入:root = [2,null,3,null,4,null,5,null,6]
输出:5

提示:

树中节点数的范围在 [0, 10^5] 内
-1000 <= Node.val <= 1000

js解决方案

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNoderoot
 * @return {number}
 */

var minDepth = function (root) {
    // 如果没有根节点,则直接返回0
    if (!root) return 0;

    //新建一个栈
    const stack = [[root, 1]];
    while (stack.length) {

        const [o, n] = stack.shift();

        // 如果左子树和右子树没子节点,则返回
        if (!o.left && !o.right) {
            return n;
        }

        if (o.left) stack.push([o.left , n + 1]);
        if (o.right) stack.push([o.right, n + 1]);
    }
};

二叉树的最大深度

leetcode地址:https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

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

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

示例 1:

web前端算法简介之树-二叉树
输入:root = [3,9,20,null,null,15,7]
输出:3

示例 2:

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

提示:

树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100

js实现方案

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNoderoot
 * @return {number}
 */

var maxDepth = function(root) {
if(!root) return 0 // 如果没有根节点,则直接返回0
  // 找左右叉的最大值
  return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1
};

翻转二叉树

leetcode地址:https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/description/

给定一棵二叉树的根节点 root,请左右翻转这棵二叉树,并返回其根节点。

示例 1:

web前端算法简介之树-二叉树
输入:root = [5,7,9,8,3,2,4]
输出:[5,9,7,4,2,3,8]

提示:

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

注意:本题与主站 226 题相同:https://leetcode-cn.com/problems/invert-binary-tree/

js代码解决方案

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNoderoot
 * @return {TreeNode}
 */

var mirrorTree = function(root) {
    // 如果根节点为空,则直接返回
    if(  root == null ) return null;

    // 定义一个临时变量,暂存左子树
    let tmp = root.left;

    // 左右子树颠倒
    root.left = root.right;
    root.right = tmp; 
    mirrorTree(root.left);
    mirrorTree(root.right); 
    return root;
};

相同的树

leetcode地址:https://leetcode.cn/problems/same-tree/description/

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

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

示例 1:

web前端算法简介之树-二叉树
输入:p = [1,2,3], q = [1,2,3]
输出:true

示例 2:

web前端算法简介之树-二叉树
输入:p = [1,2], q = [1,null,2]
输出:false

示例 3:

web前端算法简介之树-二叉树
输入:p = [1,2,1], q = [1,1,2]
输出:false

提示:

两棵树上的节点数目都在范围 [0, 100] 内
-10^4 <= Node.val <= 10^4

js代码解决方案

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNodep
 * @param {TreeNodeq
 * @return {boolean}
 */

var isSameTree = function (p, q) {
    // 如果没有则返回true
    if (p == null && q == nullreturn true

    // 如果q == null 或者q == null 则返回false
    if (p == null || q == nullreturn false

    // 如果p.val 不等于 q。val 则返回false
    if (p.val != q.val) return false

    // 否则,递归处理o和q的左子树和右子树是否相同
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)

};


原文始发于微信公众号(前端爱好者):web前端算法简介之树-二叉树

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/267067.html

(0)
李, 若俞的头像李, 若俞

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!