写点什么

前端工程师 leetcode 算法面试必备 - 简单的二叉树

作者:js2030code
  • 2022-12-13
    浙江
  • 本文字数:1878 字

    阅读完需:约 6 分钟

一、前言

  本难度的题目主要考察二叉树的基本概念和操作。

1、基本概念

  树是计算机科学中经常用到的一种非线性数据结构,以分层的形式存储数据。二叉树是一种特殊的树结构,每个节点最多有两个子树,通常子树被称作“左子树”和“右子树”。



  以上述图片为例,介绍二叉树相关的几个术语:


  • 节点的度:节点拥有子树的数量,图中节点 7 的度为 2;

  • 叶子节点:度为 0 的节点,图中节点 2 就是一个叶子节点;

  • 节点的层次:根节点的层定义为 1,根的孩子为第二层节点,依次类推;

  • 树的深度:树中的最大节点层,图中树的深度为 3;


在 JavaScript 中,可以创建 TreeNode 对象来描述树的节点:


function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
复制代码


  另外二叉树也有不同的表现形态,最常见的就是二叉查找树(Binary Search Tree),它具有以下性质:


  • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;

  • 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;

  • 任意节点的左、右子树也分别为二叉查找树;

  • 没有键值相等的节点。


二叉查找树相比较其他数据结构的优势在于查找、插入的时间复杂度较低,为 O(logn),并且对它进行中序遍历操作之后,可以得到一个有序序列,这使得它成为出题的常客

2、基本操作

  二叉树经常考察的问题主要基于以下操作:


  • 计算二叉树的深度;

  • 先序遍历:首先访问根,再先序遍历遍历左子树,最后先序遍历右子树;

  • 中序遍历:首先中序遍历左子树,再访问根,最后中序遍历右子树;

  • 后序遍历:首先后序遍历左子树,再后序遍历右子树,最后访问根;

  • 层次遍历:按照节点的层次访问;


二叉树非常适合采用递归思想处理,虽然递归非常耗费内存,但是它写出的代码可读性非常强,另外可以通过尾递归的书写方式,让 JavaScript 引擎将其优化为迭代的方式,从而大幅度地优化时间和空间的复杂度。

二、104. 二叉树的最大深度

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


  这是一道计算二叉树深度的题目,利用递归思想:不断计算子树的深度,即可得到整个二叉树的深度



相同类型的题目:


  • 【111. 二叉树的最小深度】;

三、144. 二叉树的前序遍历

给定一个二叉树,返回它的 前序 遍历。


  采用递归实现二叉树的前序遍历的代码,可读性非常强:



  同样的实现中序遍历以及后序遍历,是不是小菜一碟!

四、783. 二叉搜索树结点最小距离

给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。


  解题思路:二叉搜索树的中序遍历序列为递增序列


参考视频:传送门



  相同类型的题目:


  • 【530. 二叉搜索树的最小绝对差】;

  • 【897. 递增顺序查找树】;

  • 【653. 两数之和 IV - 输入 BST】;

五、563. 二叉树的坡度

给定一个二叉树,计算整个树的坡度。一个树的节点的坡度定义即为,该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是 0。整个树的坡度就是其所有节点的坡度之和。


  解题思路:在后序遍历的过程中,先计算左子树和值以及右子树和值,再计算当前节点的坡度,最后更新当前子树的和值



六、107. 二叉树的层次遍历 II


给定一个二叉树,返回其节点值自底向上的层次遍历。(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

1、队列和栈

  第一种方法:采用栈和队列维护每一层访问的节点



2、递归


  第二种方法:利用递归思想在前序遍历的过程中记录相应的层级



  相同类型的题目:


  • 【637. 二叉树的层平均值】;

  • 【872. 叶子相似的树】;

七、938. 二叉搜索树的范围和

给定二叉搜索树的根结点 root,返回 L 和 R(含)之间的所有结点的值的和。二叉搜索树保证具有唯一的值。


  这道题目主要考察前文提到的二叉查找树的特性,处理的方式类似于上几篇提到的二分搜索算法:



  相同类型的题目:


  • 【700. 二叉搜索树中的搜索】;

  • 【669. 修剪二叉搜索树】;

  • 【538. 把二叉搜索树转换为累加树】;

八、100. 相同的树

给定两个二叉树,编写一个函数来检验它们是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。


  解题思路:递归处理两个树的根节点、左子树和右子树,如果它们都相等,那么两个树必然相等



  相同类型的题目:


  • 【572. 另一个树的子树】;

  • 【101. 对称二叉树】;

  • 【226. 翻转二叉树】;

写在最后

  算法作为计算机的基础学科,用 JavaScript 刷,一点也不丢人ε=ε=ε=┏(゜ロ゜;)┛。


  本系列文章会分别给出一种算法的 3 种难度的总结篇(简单难度,中等难度以及困难难度)。在简单难度中,会介绍该算法的基本知识与实现,另外两个难度,着重讲解解题的思路。


  如果本文对您有所帮助,可以点赞或者关注来鼓励博主。


用户头像

js2030code

关注

还未添加个人签名 2022-09-14 加入

还未添加个人简介

评论

发布
暂无评论
前端工程师leetcode算法面试必备-简单的二叉树_JavaScript_js2030code_InfoQ写作社区