Skip to content

编码面试的树形清单

原文：https://www.techinterviewhandbook.org/algorithms/tree/

简介

树是一种广泛使用的抽象数据类型，它用一组相连的节点来表示分层结构。树中的每个节点可以连接到许多子节点，但必须连接到一个父节点，根节点除外，它没有父节点。

树是一种无向且连通的无环图。没有循环或回路。每个节点可以像它自己的子树的根节点一样，使得递归成为一种有用的树遍历技术。

出于面试的目的，你通常会被问到二叉树，而不是三元(3 个孩子)或 N 元(N 个孩子)树。在这一页，我们将涵盖二叉树和二分搜索法树，这是二叉树的一个特例。

树通常用于表示分层数据，例如文件系统、JSON 和 HTML 文档。请务必查看关于 Trie 的部分，这是一种用于高效存储和搜索字符串的高级树。

学习资源

你需要知道的常用术语

  • 邻居 -节点的父节点或子节点
  • 祖先 -通过遍历其父链可到达的节点
  • 后代 -节点子树中的一个节点
  • 度 -一个节点的子节点数
  • 树的度-树中节点的最大度
  • 距离 -两个节点间最短路径的边数
  • 级别/深度 -沿着节点和根节点之间的唯一路径的边的数量
  • 宽度 -一个级别中的节点数

二叉树

二进制意味着两个，所以二叉树中的节点最多有两个子节点。

二叉树术语

  • 完全二叉树-完全二叉树是这样一种二叉树，其中除了可能的最后一层之外，每一层都被完全填充，并且最后一层中的所有节点都尽可能靠左。
  • 平衡二叉树——一种二叉树结构，其中每个节点的左右子树的高度差不超过 1。

遍历

Tree

给定这样的树，这些是各种遍历的结果。

  • 按序遍历 -左- >根- >右
    • 结果:2，7，5，6，11，1，9，5，9
  • 前序遍历 -根- >左- >右
    • 结果:1，7，2，6，5，11，9，9，5
  • 后序遍历 -左->-右- >根
    • 结果:2，5，11，6，7，5，9，9，1

注意，二叉树的有序遍历不足以唯一地序列化一个树。还需要前序或后序遍历。

二叉查找树(英国夏令时)

对 BST 的有序遍历将使所有元素有序。

非常熟悉 BST 的属性，并验证二叉树是 BST。这个问题出现的频率比预期的要高。

当问题涉及 BST 时，面试官通常会寻找比 O(n)运行速度更快的解决方案。

时间复杂度

操作 大 O
接近 O(log(n))
搜索 O(log(n))
插入 O(log(n))
去除 O(log(n))

遍历平衡树的空间复杂度是 O(h)其中 h 是树的高度，而遍历非常偏斜的树(本质上是一个链表)将是 O(n)。

面试时要注意的事情

您应该非常熟悉递归地编写前序、按序和后序遍历。作为扩展，通过迭代地编写它们来挑战自己。有时面试官会问候选人迭代方法，尤其是当候选人太快写完递归方法的时候。

拐角情况

  • 空树
  • 单一节点
  • 两个音符
  • 非常倾斜的树(像一个链表)

常用套路

熟悉以下程序，因为许多树型问题在解决方案中使用了一个或多个这些程序:

  • 插入值
  • 删除值
  • 计算树中节点的数量
  • 值是否在树中
  • 计算树的高度
  • 二叉查找树
    • 确定是否是二叉查找树
    • 获取最大值
    • 获取最小值

技巧

使用递归

递归是遍历树的最常见的方法。当您注意到子树问题可以用来解决整个问题时，请尝试使用递归。

当使用递归时，总是记得检查基本情况，通常是节点是null的地方。

有时你的递归函数可能需要返回两个值。

按级别遍历

当你被要求逐层遍历一棵树时，使用广度优先搜索。

节点总和

如果问题涉及沿途节点的求和，一定要检查节点是否可以是负数。

基本问题

如果你在学习这个话题，这些是需要练习的基本问题。

推荐练习题

这些是在你为题目学习并练习了基本问题后推荐练习的问题。

推荐课程

AlgoMonsterT3】

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式，并有内容帮助你快速修改基本的数据结构和算法。最重要的是，AlgoMonster 不是基于订阅的——支付一次性费用，就可以获得终身访问。 今天加入七折优惠→

寻找编码面试:编码问题的模式

设计大师的这门课程扩展了推荐练习题中的问题，但从问题模式的角度来进行练习，这是一种我也同意的学习方法，我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题，并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式，而不是背答案！ 现在获得终身使用权→

掌握编码面试:数据结构+算法

这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星，21.5k 评分，135k 学生)，包含了价值 19 个小时的内容。像技术面试手册一样，它超越了编码面试，涵盖了简历，非技术面试，谈判。是一个全包！请注意，JavaScript 用于编码演示。 结账→

回到顶部