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

一、前言

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

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种难度的总结篇（简单难度，中等难度以及困难难度）。在简单难度中，会介绍该算法的基本知识与实现，另外两个难度，着重讲解解题的思路。