JS版数据结构第五篇(二叉树)

背景

二叉树算是难度相对较高的一种数据结构

它的种类很多,衍生出来的题目类型也千变万化

想要面面俱到仅仅通过一篇博客很难做到,而且效果也不会很好

由于它的基本结构以及二叉树类型题目的解决思路大致相同

所以这里我们有针对性的挑两道题目进行讲解,如果有问题大家也可以在评论区进行讨论

对称二叉树

LeetCode第101题 原题地址

题目难度: 简单

题目描述

给定一个二叉树，检查它是否是镜像对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

示例1：二叉树[1,2,2,3,4,4,3]是对称的,返回true

    1
   / \
  2   2
 / \ / \
3  4 4  3

示例2：二叉树[1,2,2,null,3,null,3]则不是镜像对称的,返回false

    1
   / \
  2   2
   \   \
   3    3

 要求: 传入root(根节点),返回true或false

题目理解

• 理解数据结构

由于这道题直接传入了已实现好的二叉树，而有的同学可能不清楚这种数据结构具体是怎样的

所以在分享解题思路之前我们先来介绍一下二叉树的数据结构(觉得啰嗦的同学可以跳过这一节)

题目中使用了数组的格式来表示二叉树的结构

(使用数组表示只是为了方便理解 并不代表二叉树是一个数组)

将二叉树的所有节点逐行从左至右排列到数组中,为每个节点的左右子节点都保留位置,如果没有则表示为null。

如[1,2,2,3,4,4,3]对应       

    1
   / \
  2   2
 / \ / \
3  4 4  3

[1,2,2,null,3,null,3]对应

    1
   / \
  2   2
   \   \
   3    3

二叉树中每一个节点可以看作是一个对象,他包含三部分:

• 节点的值val
• 指向左节点的指针left(若没有左结点默认为null)
• 指向右节点的指针right(若没有右结点默认为null)

拿示例1进行举例

    1
   / \
  2   2
 / \ / \
3  4 4  3

我们将根节点命名为root，则节点间的对应关系为:

则结合示例中给出的值我们可以得出:

• root.val = 1 
• root.left.val = 2
• root.right.val = 2 
• ...

结构我们理清了,接下来分析一下题目要求

• 分析题目要求

题目中要求传入的是一个根节点root

// root 是根节点 二叉树结构已实现
root => {
    // 如果根节点为空 返回true
    if(!root) {
        return true
    }
    // map函数用来比较两个节点是否完全相同
    // @param1{Object}节点1 
    // @param2{Object}节点1的对称点
    let map = (node1,node2) => {
        // 两个节点都不存在 返回true
        if(!node1 && !node2){
            return true
        }
        // 其中一个节点不存在或两个节点值不相等,返回false
        if(!node1 || !node2 || node1.val !== node2.val){
            return false
        }
        // 遍历当前两个对称点的子节点的对称点
        return map(node1.left, node2.right) && map(node2.right, node2.left)
    }
    // 初始传入根节点的左右节点
    return map(root.left, root.right)
}

然后对比一下我们的方法是否一致。

代码实现

// root依然为根节点,二叉树结构已生成
root => {
    // 用来记录当前最大值
    let max = -Infinity
    // map函数用来查看当前节点是否符合二叉搜索树结构
    // @param{Object} 节点    
    let map = node => {
        // 若结点为空, 返回true
        if(!node){
            return true
        }
        // 若有左节点 先递归左结点 left记录当前节点左子树是否符合二叉搜索树结构
        let l = map(node.left)
        // 判断当前节点值是否大于max
        if(node.val > max){
            max = node.val
        }else{
            return false
        }
        // 左子树递归完成且当前节点也递归完成后 递归右子树
        let r = map(node.right)
        // 左右子树都满足条件 返回true
        return l && r
    }
    // 初始传入根节点
    return map(root)
}

总结

虽然这两道题我们都仅仅用十行左右的代码就实现了功能，但是我们却用了很长的篇幅来讲

解，一方面是为了让有些不熟悉这种数据结构的同学对它有一定的了解于认识，另一方面也是

让大家更加熟悉递归的用法，熟练使用递归是每个程序员必备的能力，希望我的博客能对你有

所帮助!

我只是一名小白，大家如果有更好的实现方法一定请在评论区多多指教。