本章涵盖了面试中最棘手的话题之一：树和图表。尽管与这两个主题相关的问题很多，但实际上在面试中遇到的问题很少。因此，优先考虑树和图最流行的问题是非常重要的。

在本章中，我们将从树和图的简要概述开始。稍后，我们将解决在亚马逊、微软、Adobe 和其他公司等 IT 巨头的面试中遇到的最流行和最具挑战性的问题。到本章结束时，您将知道如何以高效和全面的方式回答面试问题并解决有关树和图的编码挑战。

本章涵盖以下主题：

• 简而言之，树木
• 简而言之图
• 编码挑战

那么，让我们开始吧！

本章中的所有代码都可以在 GitHub 上找到 https://github.com/PacktPublishing/The-Complete-Coding-Interview-Guide-in-Java/tree/master/Chapter13。

树 是一种非线性数据结构，在节点中分层组织数据，不能包含循环。一棵树有一个特定的术语，可能略有不同，但通常采用以下概念：

• Root 是 最顶层节点。
• Edge 是链接 或两个节点之间的连接。
• Parent 是一个 节点，它与子节点有一条边。
• Child 是一个具有父节点的 节点。
• Leaf 是一个没有子节点的 节点。
• Height 是到叶子的最长路径的 长度。
• Depth 是到其根路径的长度。

下图举例说明了在树上使用这些术语：

图 13.1 – 树术语

通常，任何树都可以有根。树的节点可以遵守一定的顺序（或不遵守），可以存储任何类型的数据，并且可能具有到它们的父节点的链接。

树编码挑战充斥着模棱两可的细节和/或不正确的假设。为了消除歧义，与面试官澄清每一个细节是非常重要的。最重要的方面之一是指树的类型。让我们来看看最常见的树木类型。

General tree

粗略地说，我们可以将树分类为二叉树和其余的允许树。二叉树 是一棵树，其中每个节点最多有两个子节点。在下图中，左侧图像是非二叉树，而右侧图像是二叉树：

图 13.2 – 非二叉树与二叉树

在代码方面，二叉树 可以如下塑造（这个实现在 italic">编码挑战部分，请记住这一点）：

private class Node {
  private Node left;
  private Node right;
  private final T element;
  public Node(T element) {
    this.element = element;
    this.left = null;
    this.right = null;
  }
  public Node(Node left, Node right, T element) {
    this.element = element;
    this.left = left;
    this.right = right;
  }
  // operations
}

如您所见，每个 Node 都保留对其他两个 Node 元素的引用，以及一个通用数据（元素）。左右节点代表当前节点的子节点。面试中遇到的大多数树编码挑战都使用二叉树，因此值得特别注意。二叉树可以分为以下几类。

Knowing binary tree traversal

在参加技术面试之前，你必须知道如何遍历二叉树。通常，遍历二叉树本身不会有问题，但您必须熟悉 广度优先搜索 (BFS) 和 深度优先搜索(DFS) 算法，以及它们的三种变体：Pre-Order、In-Order、和后订单。下图表示每种遍历类型的结果：

图 13.3 – 二叉树遍历

让我们简要概述一下 BFS 和 DFS 算法。

Breadth-first Search (BFS) for trees

树的 BFS 是 也称为 Level-Order 遍历。主要思想是维护一个节点队列，以确保遍历的顺序。最初，队列仅包含根节点。该算法的步骤如下：

1. 从队列中弹出第一个节点作为当前节点。
2. 访问当前节点。
3. 如果当前节点有左节点，则将该左节点入队。
4. 如果当前节点有一个正确的节点，则将该正确的节点排入队列。
5. 从 step 1 开始重复，直到队列为空。

在代码方面，我们有以下内容：

private void printLevelOrder(Node node) {
  Queue<Node> queue = new ArrayDeque<>();
  queue.add(node);
  while (!queue.isEmpty()) {
    // Step 1
    Node current = queue.poll();
    // Step 2
    System.out.print(" " + current.element);
    // Step 3
    if (current.left != null) {
      queue.add(current.left);
    }
    // Step 4
    if (current.right != null) {
      queue.add(current.right);
    }
  }
}

接下来，让我们关注 DFS。

Depth-first Search (DFS) for trees

树的 DFS 具有三种变体：Pre-Order、In-Order , 和 Post-Order。

Pre-Order遍历访问当前节点在其子节点之前，如下(root | left sub-tree | right sub-tree) ：

private void printPreOrder(Node node) {
  if (node != null) {
    System.out.print(" " + node.element);
    printPreOrder(node.left);
    printPreOrder(node.right);
  }
}

有序遍历访问左分支，然后是当前节点，最后是右分支，如下(left sub-tree | root | 右子树）：

private void printInOrder(Node node) {
  if (node != null) {
    printInOrder(node.left);
    System.out.print(" " + node.element);
    printInOrder(node.right);
  }
}

Post-Order在其子节点之后访问当前节点，如下(left sub-树 | 右子树 | 根）：

private void printPostOrder(Node node) {
  if (node != null) {
    printPostOrder(node.left);
    printPostOrder(node.right);
    System.out.print(" " + node.element);
  }
}

完整的应用程序是称为BinaryTreeTraversal。除了前面的例子，完整的代码还包含 BFS 和 DFS 实现，它们返回一个 List 和一个 Iterator。

Binary Search Tree

二叉搜索树（BST）是一个二叉树，它遵循一个排序规则。通常，在 BST 中，左后代（根左侧的所有元素）小于或等于根元素，而右后代（根右侧的所有元素） ) 大于根元素。但是，此顺序不仅仅适用于根元素。它适用于每个节点，n，因此，在 BST 中，n 的左后代 ≤ n < 对 n的后代。在下图中，左边的图像是二叉树，而右边的图像是 BST：

图 13.4 – 二叉树与 BST

通常，BST 不接受重复，但当它接受时，它们可以在一侧（例如，仅在左侧）或两侧。副本也可以存储在单独的哈希映射中，或通过计数器直接存储在树的结构中。注意并与面试官澄清这些细节。在 BST 中处理重复是一个问题在 Amazon、Flipkart 和 Microsoft 的采访中遇到，这就是为什么它将在 编码挑战中解决 部分。

在本书捆绑的代码中，您可以找到一个名为 BinarySearchTreeTraversal 的应用程序，该应用程序 公开了以下一组方法：插入（T 元素），包含（T 元素），删除（T 元素） , min(), max(), root(), < code class="literal">size() 和 height()。此外，它包含 BFS 和 DFS 的实现，用于打印节点和将节点返回为 List 或 Iterator。花点时间剖析代码。

Balanced and unbalanced binary trees

当二叉树保证插入和查找操作的时间为 O(log n) 时，我们可以说我们有一个 平衡二叉树，但它不一定是平衡的。当树中任意一个节点的左子树和右子树的高度差不大于1时，则该树为高度平衡。在下图中，左边的树是不平衡的二叉树，中间的树是平衡的但高度不平衡的二叉树，右边的树是高度平衡的树：

图 13.5 – 不平衡二叉树与平衡二叉树与高度平衡二叉树

有两种类型的平衡树：红黑树和 AVL 树。

Red-Black tree

红黑树 是一个自平衡的BST，其中每个节点都处于以下规则的事件之下：

• 每个节点不是红色就是黑色
• 根节点始终为黑色
• 每片叶子（NULL）都是黑色的
• 红色节点的两个孩子都是黑色的
• 从节点到 NULL 节点的每条路径都有相同数量的黑色节点

下图表示一棵红黑树：

图 13.6 – 红黑树示例

红黑树永远不会变得非常不平衡。如果所有节点都是黑色的，那么这棵树就变成了一个完美平衡的树。当其最长路径中的节点是交替的黑色和红色节点时，红黑树成为其最大高度。黑红树的高度总是小于等于2log2(n+1)，所以它的高度总是在O(log n)的量级。

由于它们的复杂性和实施时间，涉及红黑树的问题在面试中并不是一个常见的话题。但是，当它们发生时，问题可能会要求您执行插入、删除或查找操作。在本书附带的代码中，您可以找到一个红黑树实现，它显示了这些操作的工作情况。花点时间研究代码并熟悉 Red-Black 树的概念。该应用程序称为 RedBlackTreeImpl。

您可能想要查看的更多实现可以在 github.com/williamfiset/data-structures/blob/master/com/williamfiset/datastructures/balancedtree/RedBlackTree.java 和 algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html。对于图形可视化，请考虑 www.cs.usfca.edu/~galles/可视化/RedBlack.html。

如果你需要深入研究这个话题，我强烈建议你阅读一本专门介绍数据结构的书，因为这是一个相当广泛的话题。

AVL tree

一棵 AVL 树（以他们的发明者 Adelson-Velsky 命名Landis) 是一个自平衡的 BST，它遵守以下规则：

• 子树的高度最多可以相差 1。
• 节点（n）的平衡因子（BN）为-1、0或1，定义为高度(h) 区别：BN=h(right_subtree(n)) - h(left_subtree(n )) 或 BN=h(left_subtree(< em class="italic">n)) - h(right_subtree(n))。

下图表示 AVL 树：

图 13.7 – AVL 树示例

AVL 树允许所有操作（插入、删除、查找最小值、查找最大值等）在 O(log n) 内执行，其中 n 是节点数。

由于它们的复杂性和实施时间，涉及 AVL 树的问题在面试中并不是一个常见的话题。但是，当它们发生时，问题可能会要求您执行插入、删除或查找操作。在本书附带的代码中，您可以找到一个显示这些操作的 AVL 树实现。花点时间研究代码并熟悉 AVL 树的概念。应用程序 被称为AVLTreeImpl。

您可能想要查看的更多实现可以在 github.com/williamfiset/data-structures/blob/master/com/williamfiset/datastructures/balancedtree/AVLTreeRecursiveOptimized.java 和 algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/AVLTreeST.java.html .对于图形可视化，请考虑 www.cs.usfca.edu/~galles/可视化/AVLtree.html。

如果你需要深入研究这个话题，我强烈建议你阅读一本专门介绍数据结构的书，因为这是一个相当广泛的话题。

Complete binary tree

完全二叉树 是一棵二叉树，其中除了可能的最后一层之外，每一层都被完全填充。此外，所有节点都尽可能地向左。在下图中，左侧为不完全二叉树，右侧为完全二叉树：

图 13.8 – 不完全二叉树与完全二叉树

一棵完整的二叉树必须从左到右填充，所以上图中左侧的树是不完整的。具有 n 个节点的完整二叉树始终具有 O(log n) 高度。

Full binary tree

完整的二叉树 是一棵二叉树，其中每个节点都有两个孩子或没有孩子。换句话说，一个节点不能只有一个孩子。在下图中，左侧显示非满二叉树，而右侧显示满二叉树：

图 13.9 – 非满二叉树与满二叉树

上图中的左侧树不完整，因为节点 68 有一个子节点。

Perfect binary tree

一棵完美的二叉树同时是完整的和满的。下图显示了这样一棵树：

图 13.10 – 完美二叉树

因此，在完美二叉树中，所有叶节点都处于同一级别。这意味着最后一级包含最大数量的节点。这种树在采访中非常罕见。

重要的提示

注意听起来像这样的问题：考虑给你一棵二叉树。编写一段代码... 不要对给定的二叉树做任何假设！总是向面试官询问更多细节，例如 这是一棵平衡树吗？它是一个完整的二叉树吗？它是一个 BST 吗？。换句话说，不要将您的解决方案基于对给定二叉树可能不正确的假设。

现在，让我们更详细地讨论二进制堆。

Binary Heaps

简而言之，二叉堆 是具有堆属性的完整二叉树。当元素按升序排列时（堆属性表示每个节点的元素大于或等于其父节点的元素），我们有一个最小二叉堆（最小元素是根元素），而当它们按降序排列（堆属性表示每个节点的元素小于或等于其父元素的元素），我们有一个 Max Binary Heap（最大元素是根元素）。

下图显示了一个完整的二叉树（左侧）、一个最小二叉堆（中间）和一个最大二叉堆（右侧）：

图 13.11 – 完整的二叉树以及最小和最大堆

二进制堆未排序。它是部分有序的。任何给定级别上的节点之间都没有关系。

二叉堆通常表示为一个数组（我们将其表示为 heap），其根位于 heap[0]。更重要的是，对于 heap[i]，我们有以下内容：

• heap[(i - 1) / 2]：返回父节点
• heap[(2 * i) + 1]：返回左子节点
• heap[(2 * i) + 2]：返回右子节点

通过数组实现的最大二进制堆如下所示：

public class MaxHeap<T extends Comparable<T>> {
  private static final int DEFAULT_CAPACITY = 5;
  private int capacity;
  private int size;
  private T[] heap;
  public MaxHeap() {
    capacity = DEFAULT_CAPACITY;
    this.heap = (T[]) Array.newInstance(
      Comparable[].class.getComponentType(),DEFAULT_CAPACITY);
  }
  // operations
}

与堆一起使用的常见操作是 add()、poll()< /code> 和 peek()。添加或轮询元素后，我们必须修复堆，使其尊重堆属性。这一步通常被称为作为heapifying堆。

向堆中添加元素是一个 O(log n) 时间的操作。新元素被添加到堆树的末尾。如果新元素比它的父元素小，那么我们不需要做任何事情。否则，我们必须向上遍历堆来修复被破坏的堆属性。这个操作被称为heapify-up。 heapify-up 背后的算法有两个步骤：

1. 从堆的末尾开始作为当前节点。
2. 当当前节点有父节点且父节点小于当前节点时，交换这些节点。

从堆中轮询一个元素也是一个 O(log n) 时间的操作。在我们轮询了堆的根元素之后，我们必须修复堆以使其尊重堆属性。此操作称为 heapify-down。 heapify-down背后的算法分为三个步骤：

1. 从作为当前节点的堆的根开始。
2. 确定当前节点的子节点之间的最大节点。
3. 如果当前节点小于其最大的子节点，则交换这两个节点并从 step 2 开始重复；否则，没有别的事可做，所以停下来。

最后，窥视是一个 O(1) 操作， 返回堆的根元素。

在本书附带的代码中，您可以找到一个名为 MaxHeap 的应用程序 ，它公开了以下一组方法：添加（T 元素）、peek() 和 poll()。

重要的提示

树的一个特例是称为Trie。也称为 作为 数字树 或 前缀树， Trie 是通常用于存储字符串的有序树结构。它的名字来源于 Trie 是一个 reTrieval 数据结构。它的性能优于二叉树。我的书Java Coding Problems（https://www.packtpub.com/programming/java-coding-problems)，旁边是其他数据结构，例如元组、不相交集、二进制索引树（Fenwick 树）和 Bloom 过滤器。

接下来，让我们简要概述一下图表。

图 是一种数据结构，用于表示可以与边连接的节点集合。例如，图表可用于表示社交媒体平台上的成员网络，因此它是表示现实生活联系的绝佳数据结构。树（如上一节所述）是一种特定类型的图。换句话说，树是没有环的图。在图方面，没有循环的图是称为无环图。

图的具体术语涉及两个主要术语：

• Vertex 表示信息（例如，成员、狗或值）
• Edge 是两个顶点之间的连接或 关系

连接可以是单向的（如二叉树的情况）或双向的。当连接是双向的（例如双向街道）时，该图称为 无向图，并且它具有 无向边 。当连接是单向的（例如单向街道）时，该图称为有向图，它具有有向边< /em>。

图的边缘可以携带称为权重的信息（例如，道路的长度）。在这种情况下，这些图称为加权图。当一个图有一条边指向同一个顶点时，它被称为自环图。下图提供了每种图形类型的表示：

图 13.12 – 图表类型

与二叉树不同，通过节点链接表示图是不切实际的。在计算机中，图通常通过邻接矩阵或邻接表来表示。让我们解决前者；也就是邻接矩阵。

Adjacency matrix

邻接矩阵 由一个布尔二维数组（或仅包含 0 和 1 的整数二维数组）表示 ) 的大小为 n x n，其中 n 是顶点数.如果我们将这个二维数组表示为 矩阵， 那么 矩阵[i ][j] 如果存在从顶点 i 到顶点 j;否则为假（或 0）。下图显示了无向图的邻接矩阵示例：

图 13.13 – 无向图的邻接矩阵

为了节省空间，也可以使用位矩阵。

在加权图的情况下，邻接矩阵可以存储边的权重，而 0 可以用来表示不存在边。

基于邻接矩阵实现图可以按如下方式完成（我们需要的只是顶点列表，因为边被传递给必须作为邻接矩阵遍历图的每个方法）：

public class Graph<T> {
  // the vertices list
  private final List<T> elements;
  public Graph() {
    this.elements = new ArrayList<>();
  }
  // operations
}

我们可以用来在计算机中表示图形的另一种方法是邻接表。

Adjacency list

邻接列表 是列表的数组，其大小等于图中的顶点数。每个顶点都存储在这个数组中，它存储了一个相邻顶点的列表。换句话说，数组的索引 i 处的列表包含存储在索引 i 的数组中的顶点的相邻顶点.下图显示了无向图的邻接表示例：

图 13.14 – 无向图的邻接表

基于邻接表实现图可以如下（这里，我们使用 Map 来实现邻接表）：

public class Graph<T> {
  // the adjacency list is represented as a map
  private final Map<T, List<T>> adjacencyList;
  public Graph() {
    this.adjacencyList = new HashMap<>();
  }
  // operations
}

接下来，我们简单介绍一下图的遍历。

Graph traversal

遍历图的两种最常见的方法是通过深度优先搜索(DFS< /strong>) 和 广度优先搜索 (BFS)。让我们有一个每个的概要。 BFS 主要用于图形。

在图的情况下，我们必须考虑到图可能有循环。一个简单的 BFS 实现（正如您在二叉树的情况下看到的）没有考虑循环，因此我们在遍历 BFS 队列时冒着无限循环的风险。消除这种风险可以通过保存访问节点的附加集合来完成。该算法的步骤如下：

1. 将起始节点（当前节点）标记为已访问（将其添加到已访问节点的集合中）并将其添加到 BFS 队列中。
2. 从队列中弹出当前节点。
3. 访问当前节点。
4. 获取当前节点的相邻节点。
5. Loop the adjacent nodes. For each non-null and unvisited node, do the following:

   一个。将其标记为已访问（将其添加到已访问节点的集合中）。

   湾。将其添加到队列中。

6. 从 第 2 步 重复，直到队列为空。

Depth-first Search (DFS) for graphs

对于图，我们可以通过递归或迭代实现来实现 DFS 算法。

DFS for graphs via recursion

递归实现图 DFS算法的步骤如下：

1. 从当前节点（给定节点）开始，将当前节点标记为已访问（将其添加到已访问节点的集合中）。
2. 访问当前节点。
3. 通过递归遍历未访问的相邻顶点。

DFS for graphs – iterative implementation

DFS 算法的迭代实现依赖于堆栈。步骤如下：

1. 从当前节点（给定节点）开始，将当前节点推入Stack。
2. While Stack is not empty, do the following:

   一个。从 Stack. 中弹出当前节点

   湾。访问当前节点。

   C。将当前节点标记为已访问（将其添加到已访问节点的集合中）。

   d。将未访问的相邻顶点推入 Stack。

在本书捆绑的代码中，你可以找到一个基于邻接矩阵的图实现，称为GraphAdjacencyMatrixTraversal。你还可以找到一个基于名为 GraphAdjacencyListTraversal 的邻接列表的应用程序。 两个应用程序都包含 BFS 和 DFS 实现。

既然我们已经对树和图进行了简要概述，现在是时候用这些主题的采访中遇到的 25 个最流行的编码问题来挑战自己了。

像往常一样，我们遇到了世界顶级公司通常会遇到的各种问题，包括亚马逊、Adobe 和谷歌等 IT 巨头。那么，让我们开始吧！

Coding challenge 1 – Paths between two nodes

问题：假设您已经 获得了一个有向图。如果两个给定节点之间存在路径（路线），则编写一段代码返回 true。

解决方案：让我们考虑下图中显示的有向图：

图 13.15 – 从 D 到 E 的路径，反之亦然

如果我们考虑节点 D 和 E，那么我们可以从 D 到 E，有 3 条路径，而从 E 到 D ， 没有了。因此，如果我们从 D 开始并遍历图（通过 BFS 或 DFS），那么在某些时候，我们必须通过节点 E ，否则D和E之间将没有路径。因此，该问题的解决方案包括从给定节点之一开始并遍历 图表，直到我们到达第二个给定节点或直到没有更多有效移动。例如，我们可以通过 BFS 执行此操作，如下所示：

public boolean isPath(T from, T to) {
  Queue<T> queue = new ArrayDeque<>();
  Set<T> visited = new HashSet<>();
  // we start from the 'from' node
  visited.add(from);
  queue.add(from);
  while (!queue.isEmpty()) {
    T element = queue.poll();
    List<T> adjacents = adjacencyList.get(element);
    if (adjacents != null) {
      for (T t : adjacents) {
        if (t != null && !visited.contains(t)) {
          visited.add(t);
          queue.add(t);
          // we reached the destination (the 'to' node)
          if (t.equals(to)) {
            return true;
          }
        }
      }
    }
  }
  return false;
}

完整的应用程序是称为DirectedGraphPath。

Coding challenge 2 – Sorted array to minimal BST

亚马逊、谷歌

问题：假设您已经获得了一个排序（升序）的整数数组。编写一段代码，从这个数组创建最小的 BST。我们将最小 BST 定义为具有最小高度的 BST。

解决方案：将给定数组视为 {-2, 3, 4, 6, 7, 8, 12, 23, 90}。可以从此数组创建的最小 BST 如下所示：

图 13.16 – 排序数组到最小 BST

为了获得最小高度的 BST，我们必须努力在左右子树中分配相等数量的节点。记住这个陈述，注意我们可以选择排序数组的中间作为根。中间左边的数组元素比中间小，所以可以形成左子树。中间右边的数组元素大于中间，所以可以形成右子树。

因此，我们可以选择 7 作为树的根。接下来，-2、3、4 和 6 应该形成左子树，而 8、12、23 和 90 应该形成右子树。但是，我们知道我们不能简单地将这些元素添加到左子树或右子树，因为我们必须尊重 BST 属性：在 BST 中，对于每个节点，n, n ≤ n < 的左后代n的右后裔。

但是，我们可以简单地遵循相同的技术。如果我们把-2、3、4、6看作一个数组，那么它的中间是3，如果我们把8、12、24和90看作一个数组，那么它的中间就是12。所以，3是根左子树包含-2，右子树是包含4和6的树。同理，12是左子树的根，包含8，右子树的根-sub-tree 是包含 24 和 90 的树。

好吧，我认为我们有足够的 经验来直觉可以应用相同的技术，直到我们处理完所有子数组。此外，可以通过递归实现此解决方案非常直观（如果您不认为递归是您的主要技能之一，请查看 第 8 章，递归和动态规划）。因此，我们可以分四步恢复我们的算法：

1. 将数组的中间元素插入树中。
2. 将左子数组的元素插入左子树。
3. 将右子数组的元素插入右子树。
4. 触发递归调用。

以下实现将这些步骤放入代码中：

public void minimalBst(T m[]) {       
  root = minimalBst(m, 0, m.length - 1);
}
private Node minimalBst(T m[], int start, int end) {
  if (end < start) {
    return null;
  }
  int middle = (start + end) / 2;
  Node node = new Node(m[middle]);
  nodeCount++;
  node.left = minimalBst(m, start, middle - 1);
  node.right = minimalBst(m, middle + 1, end);
  return node;
}

完整的 应用程序称为 SortedArrayToMinBinarySearchTree。

Coding challenge 3 – List per level

问题：假设你已经给定了一棵二叉树。编写一段代码，为树的每个级别创建一个元素列表（例如，如果树的深度为 d，那么您将拥有 d 列表）。

解决方案：让我们考虑下图中所示的二叉树：

图 13.17 – 每个级别的列表

所以，我们有一个深度为 3 的二叉树。在深度 0 上，我们有根 40。在深度 1 上，我们有 47 和 45。在深度 2 上，我们有 11、13、44 和 88。最后，在深度 3，我们有 3 和 1。

这么想是很直观的：如果我们逐层遍历二叉树，那么我们可以为每一层创建一个元素列表。换句话说，我们可以调整 BFS 算法（也称为 Level-Order 遍历），以便我们捕获每个遍历级别的元素。更准确地说，我们首先遍历根（并创建一个包含该元素的列表），然后遍历第 1 层（并创建一个包含该层元素的列表），依此类推。

当我们到达层i时，我们将已经完全访问了上一层的所有节点，我-1。这意味着要获取级别 i 上的元素，我们必须遍历上一级节点的所有子节点 i -1。以下解决方案在 O(n) 时间内运行：

public List<List<T>> fetchAllLevels() {
  // each list holds a level
  List<List<T>> allLevels = new ArrayList<>();
  // first level (containing only the root)
  Queue<Node> currentLevelOfNodes = new ArrayDeque<>();
  List<T> currentLevelOfElements = new ArrayList<>();
  currentLevelOfNodes.add(root);
  currentLevelOfElements.add(root.element);
  while (!currentLevelOfNodes.isEmpty()) {
    // store the current level as the previous level
    Queue<Node> previousLevelOfNodes = currentLevelOfNodes;
    // add level to the final list
    allLevels.add(currentLevelOfElements);
    // go to the next level as the current level
    currentLevelOfNodes = new ArrayDeque<>();
    currentLevelOfElements = new ArrayList<>();
    // traverse all nodes on current level
    for (Node parent : previousLevelOfNodes) {
      if (parent.left != null) {
        currentLevelOfNodes.add(parent.left);                    
        currentLevelOfElements.add(parent.left.element);
      }
      if (parent.right != null) {
        currentLevelOfNodes.add(parent.right);                      
        currentLevelOfElements.add(parent.right.element);
      }
    }
  }
  return allLevels;
}

完整的 应用程序称为ListPerBinaryTreeLevel。

Coding challenge 4 – sub-tree

Adobe、微软、Flipkart

问题：假设您已经 给定了两个二叉树，p 和q。如果 q 是 p< 的子树，则编写返回 true 的代码片段/em>。

解决方案：考虑下图：

图 13.18 – 二叉树的另一个二叉树的子树

可以看到，中间的二叉树q是p1二叉树的子树（左-hand 侧）但不是 p2 二叉树的子树（右侧）。

此外，该图揭示了两种情况：

• 如果 p 的根与 q 的根匹配 (p.root.element == q.root.element)，那么问题归结为检查q的右子树是否与p, 或者 q 的左子树是否与 的左子树相同p。
• 如果 p 的根不匹配 q (p.root. element != q.root.element)，那么问题归结为检查 p 的左子树是否与 q, 或者 p 的右子树是否与 q 相同。

为了实现第一个 项目符号，我们需要两个方法。为了更好地理解为什么我们需要两种方法，请查看下图：

图片 13.19 – 根和叶匹配但中间节点不匹配

如果 p 和 q 的根匹配但左/右子树的某些节点不匹配，然后我们必须回到我们从 p 和 q 开始的地方来检查是否有 q 是 p 的子树。第一种方法应该在它们的根相同时检查树是否相同。第二种方法应该处理我们发现树不相同但从某个节点开始的情况。注意这方面，因为许多候选人没有考虑到这一点。

因此，就代码而言，我们有以下内容（对于 n 个节点，这在 O(n) 时间内运行）：

public boolean isSubtree(BinaryTree q) {
  return isSubtree(root, q.root);
}
private boolean isSubtree(Node p, Node q) {
  if (p == null) {
    return false;
  }
  // if the roots don't match
  if (!match(p, q)) {
    return (isSubtree(p.left, q) || isSubtree(p.right, q));
  }
  return true;
}
private boolean match(Node p, Node q) {
  if (p == null && q == null) {
    return true;
  }
  if (p == null || q == null) {
    return false;
  }
  return (p.element == q.element
      && match(p.left, q.left)
      && match(p.right, q.right));
}

该应用程序是，称为BinaryTreeSubtree。

Coding challenge 5 – Landing reservation system

亚马逊、Adobe、微软

问题：考虑一个只有一条跑道的机场。该机场接收来自不同飞机的着陆请求。着陆请求包含着陆时间（例如，9:56）和完成程序所需的时间（例如，5 分钟）。我们将其表示为 9:56 (5)。编写一段代码，使用 BST 来设计这个预订系统。由于只有一条跑道，代码应该拒绝任何与现有跑道重叠的着陆请求。请求的顺序决定了保留的顺序。

解决方案：我们来看一张我们登陆时间线的时间截图（登陆请求的顺序是10:10 (3), 10:14 (3), 9:55 (2 )、10:18 (1)、9:58 (5)、9:47 (2)、9:41 (2)、10:22 (1)、9:50 (6) 和 10:04 (4 ). 这可以在下图中看到：

图 13.20 – 时间线截图

所以，我们已经做了几次预约，如下：9:41，一架飞机降落，需要2分钟完成程序； 9点47分和9点55分，还有另外两架飞机需要2分钟才能完成着陆； 9点58分，我们有一架飞机需要5分钟才能完成着陆；等等。此外，图中还有两个新的登陆请求，分别表示为 R1 和 R2。

请注意，我们无法批准 R1 登陆请求。着陆时间是9:50，需要6分钟才能完成，所以9:56结束。但是，在 9 点 56 分，我们已经有 9 点 55 分的飞机在跑道上。由于我们只有一条跑道，我们拒绝这个着陆请求。我们认为这种情况是重叠的。

另一方面，我们批准了 R2 登陆请求。请求时间为 10:04，需要 4 分钟才能完成，所以在 10:08 结束。在 10:08，跑道上没有其他飞机，因为下一次着陆是在 10:10。

请注意，我们必须使用 BST 来解决这个问题，但使用数组（已排序或未排序）或链表（已排序或未排序）也是一种有效的方法。使用未排序的数组（或链表）将需要 O(1) 时间来插入登陆请求，并且需要 O(n) 时间来检查潜在的重叠。如果我们要使用排序数组（或链表）和二分搜索算法，那么我们可以检查 O(log n) 中的潜在重叠。但是，要插入登陆请求，我们需要 O(n)，因为我们必须将所有元素从插入位置向右移动 。

使用 BST 怎么样？首先，让我们将前面的时间线屏幕截图表示为 BST。查看下图（登陆请求的顺序是10:10（3）、10:14（3）、9:55（2）、10:18（1）、9:58（5）、9）： 47 (2)、9:41 (2)、10:22 (1)、9:50 (6) 和 10:04 (4))：

图 13.21 – 作为 BST 的时间线截图

这一次，对于每个登陆请求，我们只需要扫描树的一半。这就是使用 BST 的结果（左边的所有节点都小于右边的所有节点，所以一个登陆请求时间只能在左子树或右子树中）。例如，10:04 的登陆请求小于根（10:10），所以它进入左子树。如果在任何给定的登陆请求中，我们遇到重叠，那么我们只是返回而不将相应的节点插入到树中。我们可以在 O(h) 中找到潜在的重叠，其中 h 是 BST 的高度，我们可以在 O(1) 时间内插入它。

以下简单计算给出了重叠（我们使用的是 Java 8 Date-Time API，但您也可以将其简化为简单的整数 - 如果您不熟悉 Java 8 Date-Time API，那么我强烈建议您购买我的书，Java Coding Problems，由 Packt (https://www.packtpub.com/programming/java-coding-problems)。这本书有一个关于这个主题的惊人的章节这是任何候选人的必读：

long t1 = Duration.between(current.element.
  plusMinutes(current.time), element).toMinutes();
long t2 = Duration.between(current.element,   
  element.plusMinutes(time)).toMinutes();
if (t1 <= 0 && t2 >= 0) {
    // overlapping found
}

因此，在 t1 中，我们计算了 (着陆时间 + 到complete) 和当前请求的登陆时间。在t2中，我们计算当前节点的落地时间和(当前请求登陆时间 + 完成所需时间）。如果 t1 小于或等于 t2，那么我们发现了重叠，所以我们拒绝当前的登陆请求。让我们看看完整的代码：

public class BinarySearchTree<Temporal> {
  private Node root = null;
  private class Node {
    private Node left;
    private Node right;
    private final LocalTime element;
    private final int time;
    public Node(LocalTime element, int time) {
      this.time = time;
      this.element = element;
      this.left = null;
      this.right = null;
    }
    public Node(Node left, Node right, 
            LocalTime element, int time) {
      this.time = time;
      this.element = element;
      this.left = left;
      this.right = right;
    }
  }
  public void insert(LocalTime element, int time) {
    if (element == null) {
      throw new IllegalArgumentException("...");
    }
    root = insert(root, element, time);
  }
  private Node insert(Node current, 
          LocalTime element, int time) {
    if (current == null) {
      return new Node(element, time);
    }
    long t1 = Duration.between(current.element.
        plusMinutes(current.time), element).toMinutes();
    long t2 = Duration.between(current.element, 
        element.plusMinutes(time)).toMinutes();
    if (t1 <= 0 && t2 >= 0) {
      System.out.println("Cannot reserve the runway at "
        + element + " for " + time + " minutes !");
      return current;
    }
    if (element.compareTo(current.element) < 0) {
      current.left = insert(current.left, element, time);
    } else {
      current.right = insert(current.right, element, time);
    }
    return current;
  }
  public void printInOrder() {
    printInOrder(root);
  }
  private void printInOrder(Node node) {
    if (node != null) {
      printInOrder(node.left);
      System.out.print(" " + node.element
        + "(" + node.time + ")");
      printInOrder(node.right);
    }
  }
}

注意，我们可以通过使用 BST 的 In-Order 遍历轻松打印时间线。完整的应用程序 称为BinaryTreeLandingReservation。

Coding challenge 6 – Balanced binary tree

亚马逊、微软

问题：假设您已经获得了一棵二叉树。如果任何节点的两个子树的高度相差不超过一，我们认为它是平衡的（这就是我们所说的高度平衡二叉树）。如果二叉树是平衡的，则编写一段返回 true 的代码片段。

解决方案：所以，为了有一个平衡的二叉树，对于每个节点，两个子树的高度差不能超过一个。符合这个说法，右图表示平衡二叉树，左图表示不平衡二叉树：

图 13.22 – 不平衡和平衡二叉树

左边的二叉树是不平衡的，因为节点 40（根）和 30 对应的左子树与右子树的高度之差大于 1（例如，左高度(40) = 4 而右高度(40) = 2)。

右侧二叉树是平衡的，因为对于每个节点，左子树和右子树的高度之差不大于一。

基于这个例子，我们可以直觉到一个简单的解决方案是由一个递归算法组成的。我们可以遍历每个节点并计算左右子树的高度。如果这些高度之间的差大于 1，那么我们返回 false。就代码而言，这是非常简单的：

public boolean isBalanced() {
  return isBalanced(root);
}
private boolean isBalanced(Node root) {
  if (root == null) {
    return true;
  }
  if (Math.abs(height(root.left) - height(root.right)) > 1) {
    return false;
  } else {
    return isBalanced(root.left) && isBalanced(root.right);
  }
}
private int height(Node root) {
  if (root == null) {
    return 0;
  }
  return Math.max(height(root.left), height(root.right)) + 1;
}

这种方法在 O(n log n) 时间内执行，因为在每个节点上，我们通过其整个子树应用递归。所以，问题是 height() 调用的数量。此时，height() 方法只计算高度。但也可以改进检查树是否平衡。我们需要做的就是通过错误代码向不平衡的子树发出信号。另一方面，对于平衡树，我们返回相应的高度。我们可以使用 Integer.MIN_VALUE 代替错误代码，如下所示：

public boolean isBalanced() {
  return checkHeight(root) != Integer.MIN_VALUE;
}
private int checkHeight(Node root) {
  if (root == null) {
    return 0;
  }
  int leftHeight = checkHeight(root.left);
  if (leftHeight == Integer.MIN_VALUE) {
    return Integer.MIN_VALUE; // error 
  }
  int rightHeight = checkHeight(root.right);
  if (rightHeight == Integer.MIN_VALUE) {
    return Integer.MIN_VALUE; // error 
  }
  if (Math.abs(leftHeight - rightHeight) > 1) {
    return Integer.MIN_VALUE; // pass error back
  } else {
    return Math.max(leftHeight, rightHeight) + 1;
  }
}

此代码在O(n)时间和O(h)空间中运行，其中h是 树。该应用程序名为 BinaryTreeBalanced。

Coding challenge 7 – Binary tree is a BST

亚马逊、谷歌、Adobe、微软，Flipkart

问题：假设你得到了一棵可能包含重复项的二叉树。编写一段代码，返回 true 如果这棵树 是 二叉搜索树 (BST)。

解决方案：从一开始，我们就注意到问题明确提到给定的二叉树可能包含重复项。为什么这很重要？因为如果二叉树不允许重复，那么我们可以依靠简单的中序遍历和数组。如果我们将每个遍历的元素添加到一个数组中，那么只有当二叉树是 BST 时，才会对结果数组进行排序。让我们通过下图阐明这方面：

图 13.23 – 有效和无效的 BST

我们知道 BST 属性表示，对于 BST 的每个节点 n， n ≤ n < 的左后代n的右后裔。这意味着上图中显示的前两棵二叉树是有效的 BST，而最后一棵不是有效的 BST。现在，将中间二叉树和最后一棵二叉树的元素添加到数组中，将得到一个 [40, 40] 的数组。这意味着我们无法基于此数组验证或使 BST 无效，因为我们无法区分树。所以，总而言之，如果给定的二叉树不接受重复，你应该依赖这个简单的算法。

现在，是时候更进一步了。让我们检查一下 n ≤ n 的左后代。以下二叉树中显示的 n 语句的右后代：

图 13.24 – 无效的 BST

看一下这个！对于每个节点 n，我们可以写成 n.left ≤ n < n.right，但很明显 55 放错了位置。所以，让我们强化一下，当前节点的所有左节点都应该小于或等于当前节点，而当前节点必须小于所有右节点。

也就是说，仅仅验证当前节点的左右节点是不够的。我们必须针对一系列节点验证每个节点。更准确地说，左子树或右子树的所有节点都应针对由最小接受元素和最大接受元素（min, max）界定的范围进行验证.让我们考虑以下树：

图 13.25 – 验证 BST

我们从根 (40) 开始，我们考虑 (min=null, max=null)，所以 40 满足条件因为没有最小或最大限制。接下来，我们转到左子树（让我们将此子树表示为 40-left-sub-tree）。来自 40-left-sub-tree 的所有节点都应该在 (null, 40) 之间。接下来，我们再次向左走，我们遇到了 35-left-sub-tree，它的范围应该在 (null, 35) 之间。基本上，我们继续向左走，直到没有节点为止。此时，我们开始向右移动，所以 35 右子树应该在 (35, 40) 之间，40 右子树应该在 (40, null) 之间，以此类推。因此，当我们向左移动时，最大值会更新。当我们向右移动时，最小值会更新。如果出现任何问题，我们将停止并返回 false。让我们看一下基于这个算法的代码：

public boolean isBinarySearchTree() {
  return isBinarySearchTree(root, null, null);
}
private boolean isBinarySearchTree(Node node, 
        T minElement, T maxElement) {
  if (node == null) {
    return true;
  }
  if ((minElement != null && 
    node.element.compareTo(minElement) <= 0)
       || (maxElement != null && node.element.
              compareTo(maxElement) > 0)) {
    return false;
  }
  if (!isBinarySearchTree(node.left, minElement, node.element)
          || !isBinarySearchTree(node.right, 
                node.element, maxElement)) {
    return false;
  }
  return true;
}

完整的应用程序 称为BinaryTreeIsBST。

Coding challenge 8 – Successor node

谷歌、微软

问题：假设您已经获得了一个二叉搜索树（< strong class="bold">BST) 和这棵树的一个节点。编写一段代码，在有序遍历的上下文中打印给定节点的后继节点。

解决方案：那么，让我们回忆一下二叉树的有序遍历。这种深度优先搜索（DFS）风格遍历左子树，然后是当前节点，然后是右子树-树。现在，假设我们从 BST 中任意选择一个节点（我们将其表示为 n）并且我们想要找到它的后继者（我们将其表示为 s) 在按顺序遍历的上下文中。

让我们将下图视为给定的 BST。我们可以用它来支持区分可能的情况：

图 13.26 – 带有起始节点和后继节点的 BST 样本

如上图所示，我们将两种主要情况表示为（a）和（b）。在情况 (a) 中，节点 n 具有右子树。在情况 (b) 中，节点 n 不包含右子树。

案例 (a)，以左侧 BST 为例，表明如果节点 n 具有右子树，则后继节点 s, 是这个右子树的最左边的节点。例如，对于 n=50，后继节点为 54。

案例（b）有两个子案例：一个简单案例和一个棘手案例。简单的案例以上图中的中间 BST 为例。当节点 n 不包含右子树并且 n 是其父节点的左子节点时，则后继节点就是这个父节点。例如，对于 n=40，后继节点为 50。这是 (b) 的简单子情况。

(b) 的棘手子情况由上图中所示的右侧 BST 举例说明。当节点 n 不包含右子树且 n 是其父节点的右子节点时，则我们必须向上遍历，直到 n 成为其父级的左孩子。完成后，我们返回这个父级。例如，如果 n=59，则后继节点为 60。

此外，我们必须考虑，如果n是遍历的最后一个节点，那么我们返回根的父节点，可以是无效的。

如果我们将这些情况粘合起来形成一些伪代码，那么我们会得到以下结果：

Node inOrderSuccessor(Node n) {
  if (n has a right sub-tree) {
    return the leftmost child of right sub-tree
  } 
  while (n is a right child of n.parent) {
    n = n.parent; // traverse upwards 
  }
  return n.parent; // parent has not been traversed
}

现在，我们可以把这个伪代码翻译成代码，如下：

public void inOrderSuccessor() {
  // choose the node
  Node node = ...;
  System.out.println("\n\nIn-Order:");
  System.out.print("Start node: " + node.element);
  node = inOrderSuccessor(node);
  System.out.print(" Successor node: " + node.element);
}
private Node inOrderSuccessor(Node node) {
  if (node == null) {
    return null;
  }
  // case (a)
  if (node.right != null) {
    return findLeftmostNode(node.right);
  }
  // case (b)
  while (node.parent != null && node.parent.right == node) {
    node = node.parent;
  }
  return node.parent;
}

完整的 应用程序称为BinarySearchTreeSuccessor。 这 应用程序也包含相同的问题，但通过 Pre-Order 和 Post-Order 遍历解决。在检查 Pre-Order 和 Post-Order 上下文的解决方案之前，您应该通过识别可能的情况并绘制伪代码及其实现来挑战自己。

Coding challenge 9 – Topological sort

亚马逊、谷歌、Adobe、微软，Flipkart

问题：考虑给你一个有向无环图（< strong class="bold">DAG);也就是没有环的有向图。编写一段代码，它返回顶点的线性排序，使得对于每个有向边，XY，顶点X 在顺序中位于 Y 之前。换句话说，对于每条边，源节点都在目的地之前。这也称为拓扑排序，它仅适用于 DAG。

解决方案：让我们通过以下 DAG 深入研究这个问题：

图 13.27 – 有向无环图（DAG）

让我们从顶点 D 开始拓扑排序。在顶点 D 之前，没有其他顶点（没有边），所以我们可以将 D 添加到结果中，（D）。从D，我们可以去B或A。让我们去顶点A。我们不能将A添加到结果中，因为我们没有处理边BA的顶点B，所以让我们去顶点B。在B之前，我们只有D ，它被添加到结果中，因此我们可以将 B 添加到结果中，(D, B)。从B，我们可以到A、E、C和F。我们不能去C，因为我们没有处理AC，我们不能去F，因为我们没有处理CF。但是，我们可以去 A，因为 DA 和 BA 已经处理过了，我们可以去 E，因为在 E 之前，只有 B，它在结果中。请注意，拓扑排序可能会提供不同的结果。让我们转到 E。因此，将 E 添加到结果 (D, B, E) 中。接下来，我们可以将 A 添加到结果中，这允许我们添加 C，这允许我们添加 F。所以，现在的结果是 (D, B, E, A, C, F)。从F，我们可以到G。由于EG已经被处理，我们可以将G添加到结果中。最后，从 G 到 H，得到拓扑排序结果为 (D, B, E, A, C, F, G, H)。

这种遍历只是一个 任意遍历，我们无法将其放入代码中。但是，我们知道可以通过 BFS 和 DFS 算法遍历图。如果我们尝试在 DFS 的上下文中思考，那么我们从节点 D 开始，遍历 B、A、C、F、G、H 和 E。在执行 DFS 遍历时，我们不能简单地将顶点添加到结果，因为我们打破了问题要求（对于每个有向边，XY，顶点 X 在 Y 在订购中）。但是，我们可以使用 Stack 并在遍历所有邻居后将顶点推入此堆栈。这意味着 H 是第一个被压入堆栈的顶点，然后是 G、F、C、A、E、B 和 D。现在，从堆栈中弹出直到它为空将给我们作为 D 的拓扑排序， B、E、A、C、F、G 和 H。

因此，拓扑排序只是一种基于 Stack 的 DFS 风格，可以按如下方式实现：

public Stack<T> topologicalSort(T startElement) {
  Set<T> visited = new HashSet<>();
  Stack<T> stack = new Stack<>();
  topologicalSort(startElement, visited, stack);
  return stack;
}
private void topologicalSort(T currentElement, 
      Set<T> visited, Stack<T> stack) {
  visited.add(currentElement);
  List<T> adjacents = adjacencyList.get(currentElement);
  if (adjacents != null) {
    for (T t : adjacents) {
      if (t != null && !visited.contains(t)) {
        topologicalSort(t, visited, stack);
        visited.add(t);
      }
    }
  }
  stack.push(currentElement);
}

完整的 应用程序称为GraphTopologicalSort。

Coding challenge 10 – Common ancestor

亚马逊、谷歌、微软、 Flipkart

问题：假设您已经 获得了一棵二叉树。编写一段代码，找到两个给定节点的第一个共同祖先。您不能在数据结构中存储其他节点。

解决方案：分析此类问题的最佳方法是拿一些纸和一支笔，用一些样本绘制一棵二叉树。请注意，问题并不是说这是 BST。实际上，它可以是任何有效的二叉树。

在下图中，我们有三种可能的情况：

图 13.28 – 寻找第一个共同祖先

在这里，我们可以看到给定的节点可以在不同的子树（左手树和右手树）中，也可以在同一子树中（中间树）。因此，我们可以使用 commonAncestor(Node root, Node n1, Node n2) 类型的方法从根开始遍历树，并返回如下（n1 和 n2 是两个给定的节点）：

• 如果根的子树包含 n1（并且不包含 n2<，则返回 n1 /em>)
• 如果根的子树包含 n2（并且不包含 n1<，则返回 n2 /em>)
• 如果 n1 和 n2 都不在根的子树中，则返回 null
• 否则，它返回 n1 和 n2 的共同祖先。

当 commonAncestor(n.left, n1, n2) 和 commonAncestor(n.right, n1, n2) 返回非空值，这意味着 n1 和 n2 在不同的子树中并且 n 是共同的祖先。让我们从代码的角度来看：

public T commonAncestor(T e1, T e2) {
  Node n1 = findNode(e1, root);
  Node n2 = findNode(e2, root);
  if (n1 == null || n2 == null) {
    throw new IllegalArgumentException("Both nodes 
             must be present in the tree");
  }
  return commonAncestor(root, n1, n2).element;
}
private Node commonAncestor(Node root, Node n1, Node n2) {
  if (root == null) {
    return null;
  }
  if (root == n1 && root == n2) {
    return root;
  }
  Node left = commonAncestor(root.left, n1, n2);
  if (left != null && left != n1 && left != n2) {
    return left;
  }
  Node right = commonAncestor(root.right, n1, n2);
  if (right != null && right != n1 && right != n2) {
    return right;
  }
  // n1 and n2 are not in the same sub-tree
  if (left != null && right != null) {
    return root;
  } else if (root == n1 || root == n2) {
    return root;
  } else {
    return left == null ? right : left;
  }
}

完整的应用程序是 称为BinaryTreeCommonAncestor。

Coding challenge 11 – Chess knight

亚马逊、微软、Flipkart

问题：假设你得到了一个 棋盘和一个马。最初，骑士被放置在一个单元格（起始单元格）中。编写一段代码，计算将骑士从起始单元格移动到给定目标单元格所需的最小移动次数。

解决方案：我们来看一个例子。棋盘大小为 8x8，马从单元格 (1, 8) 开始。目标单元格是 (8, 1)。如下图所示，骑士需要至少移动 6 步才能从单元格 (1, 8) 移动到单元格 (8, 1)：

图片 13.29 – 将骑士从单元格 (1, 8) 移动到单元格 (8, 1)

如图所示，骑士可以从一个 (r, c) 单元格移动到其他八个有效单元格，如下所示： (r +2, c+1), (r+1, c +2), (r-1,c+2), (r -2, c+1), (r-2, c -1), (r-1, c-2), (r+1、c-2) 和 (r+2, c-1)。所以，有八种可能的动作。如果我们将这些可能的运动视为方向（边）， 将单元格视为顶点，那么我们可以在图的上下文中可视化这个问题。边缘是可能的移动，而顶点是骑士可能的单元格。每次移动都保存从当前单元格到起始单元格的距离。对于每一次移动，距离都会增加 1。因此，在图的上下文中，问题归结为在图中找到最短路径。因此，我们可以使用 BFS 来解决这个问题。

该算法的步骤如下：

1. 创建一个空队列。
2. 将起始单元排入队列，使其与自身的距离为 0。
3. As long as the queue is not empty, do the following:

   一个。从队列中弹出下一个未访问的单元格。

   湾。如果弹出的单元格是目标单元格，则返回其距离。

   C。如果弹出的单元格不是目标单元格，则将此单元格标记为已访问，并通过将距离增加 1 将八个可能的移动中的每一个排入队列。

由于我们依赖于 BFS 算法，我们知道所有最短路径为 1 的单元都会被首先访问。接下来，被访问的cell是最短路径为1+1=2的相邻cell，以此类推；因此任何单元格的最短路径等于其父单元的最短路径+ 1。这意味着当我们第一次遍历目标单元格时，它会给我们最终的结果.这是 最短路径。让我们看看代码：

private int countknightMoves(Node startCell, 
            Node targetCell, int n) {
  // store the visited cells
  Set<Node> visited = new HashSet<>();
  // create a queue and enqueue the start cell
  Queue<Node> queue = new ArrayDeque<>();
  queue.add(startCell);
  while (!queue.isEmpty()) {
    Node cell = queue.poll();
    int r = cell.r;
    int c = cell.c;
    int distance = cell.distance;
    // if destination is reached, return the distance
    if (r == targetCell.r && c == targetCell.c) {
      return distance;
    }
    // the cell was not visited
    if (!visited.contains(cell)) {
      // mark current cell as visited
      visited.add(cell);
      // enqueue each valid movement into the queue 
      for (int i = 0; i < 8; ++i) {
        // get the new valid position of knight from current
        // position on chessboard and enqueue it in the queue 
        // with +1 distance
        int rt = r + ROW[i];
        int ct = c + COL[i];
        if (valid(rt, ct, n)) {
          queue.add(new Node(rt, ct, distance + 1));
        }
      }
    }
  }
  // if path is not possible
  return Integer.MAX_VALUE;
}
// Check if (r, c) is valid    
private static boolean valid(int r, int c, int n) {
  if (r < 0 || c < 0 || r >= n || c >= n) {
    return false;
  }
  return true;
}

应用程序是称为ChessKnight。

Coding challenge 12 – Printing binary tree corners

亚马逊、谷歌

问题：假设您已经 获得了一棵二叉树。编写一段代码，在每个级别打印这棵树的角。

解决方案：让我们考虑以下树：

图 13.30 – 打印二叉树角

所以，主要思想是在每一层打印最左边和最右边的节点。这意味着 Level-Order 遍历 (BFS) 很有用，因为我们可以遍历每个级别。我们所要做的就是识别 每一层的第一个和最后一个节点。为此，我们需要通过添加一个用于确定当前节点是否代表角点的条件来调整经典的 Level-Order 遍历。代码不言自明：

public void printCorners() {
  if (root == null) {
    return;
  }
  Queue<Node> queue = new ArrayDeque<>();
  queue.add(root);
  int level = 0;
  while (!queue.isEmpty()) {
    // get the size of the current level
    int size = queue.size();
    int position = size;
    System.out.print("Level: " + level + ": ");
    level++;
    // process all nodes present in current level
    while (position > 0) {
      Node node = queue.poll();
      position--;
      // if corner node found, print it
      if (position == (size - 1) || position == 0) {
        System.out.print(node.element + " ");
      }
      // enqueue left and right child of current node
      if (node.left != null) {
        queue.add(node.left);
      }
      if (node.right != null) {
        queue.add(node.right);
      }
    }
    // level done            
    System.out.println();
  }
}

应用程序是称为BinaryTreePrintCorners。

Coding challenge 13 – Max path sum

亚马逊、谷歌、Adobe、微软，Flipkart

问题：假设您已 获得一棵非空二叉树。编写一段代码来计算最大路径和。路径被认为是从任何节点开始到树中任何节点结束的任何节点序列，以及父子连接。路径必须至少包含一个节点，并且可能会或可能不会通过树的根。

解决方案：下图显示了最大路径和的三个示例：

图 13.31 – 最大路径和的三个示例

找到这个问题的解决方案需要我们确定当前节点可以成为最大路径的一部分的方式数量。通过检查前面的示例，我们可以分离出四种情况，如下图所示（花点时间查看更多示例，直到得出相同的结论）：

图 13.32 – 当前节点可以成为最大路径一部分的方式数

因此，作为 max 路径一部分的节点被置于以下四种情况之一：

1. 该节点是最大路径中的唯一节点
2. 该节点是其左子节点旁边的最大路径的一部分
3. 该节点是其右孩子旁边的最大路径的一部分
4. 该节点是其左右子节点旁边的最大路径的一部分

这四个步骤使我们得出一个明确的结论：我们必须遍历树的所有节点。一个不错的选择是 DFS 算法，但更准确地说，是 Post-Order 树遍历，它将遍历顺序强加为 left sub-tree | 右子树| 根。当我们遍历树时，我们将树其余部分的最大值传递给父级。下图显示了该算法：

图 13.33 – 后序遍历并将树中的最大值传递给父节点

因此，如果我们将这个算法一步一步地应用到上图，我们会得到以下结果（请记住，这是一个后序遍历）：

• 41没有孩子，所以41加到max(0, 0), 41+max(0, 0)=41。
• 3只有左孩子，-5，所以3加到max(-5, 0), 3+max(-5, 0)=3。
• -2 被添加到 max(41, 3) 子树中，所以 -2+max(41, 3)=39。
• -7 没有子级，所以 max(0, 0) 加上 -7，-7+max(0, 0)=-7。
• 70没有孩子，所以max(0, 0)加上70，70+max(0, 0)=70。
• -1 被添加到 max(-7, 70) 个子树中，所以 -1+70=69。
• 50 被添加到左（39）和右（69）子树的最大值，所以 39+69+50=158（这是最大路径和）。

以下代码揭示了该算法的实现：

public int maxPathSum() {
  maxPathSum(root);
  return max;
}
private int maxPathSum(Node root) {
  if (root == null) {
    return 0;
  }
  // maximum of the left child and 0
  int left = Math.max(0, maxPathSum(root.left));
  // maximum of the right child and 0
  int right = Math.max(0, maxPathSum(root.right));
  // maximum at the current node (all four cases 1,2,3 and 4)
  max = Math.max(max, left + right + root.element);
  //return the maximum from left, right along with current               
  return Math.max(left, right) + root.element;
}

应用程序是，称为BinaryTreeMaxPathSum。

Coding challenge 14 – Diagonal traversal

亚马逊、Adobe、微软

问题：假设你已经给定了一个非空二叉树。编写一段代码，打印每个负对角线 (\) 的所有节点。负对角线具有负斜率。

解决方案：如果您不熟悉二叉树负对角线的概念，请确保您与面试官澄清这方面。他们可能会为您提供一个示例，类似于下图所示的示例：

图 13.34 – 二叉树的负对角线

在上图中，我们有三个对角线。第一条对角线包含节点 50、12 和 70。第二条对角线包含节点 45、3、14 和 65。最后，第三条对角线包含节点 41 和 11。

Recursion-based solution

解决这个问题的一种方法 是使用递归和散列（如果您不熟悉散列的概念，请阅读第 6 章，面向对象编程，< em class="italic"> 哈希表 问题）。在 Java 中，我们可以通过内置的 HashMap 实现来使用哈希，因此无需从头开始编写哈希实现。但是这个 HashMap 有什么用呢？我们应该在这个映射的条目（键值对）中存储什么？

我们可以将二叉树中的每个对角线与映射中的键相关联。由于每个对角线（键）包含多个节点，因此将值表示为 List 非常方便。当我们遍历二叉树时，我们需要将当前节点添加到正确的 List 中，所以在正确的对角线下。例如，在这里，我们可以执行 Pre-Order 遍历。每次走到左子树，对角线加1，每次走到右子树，保持当前对角线。这样，我们得到类似于以下的东西：

图 13.35 – Pre-Order 遍历和左孩子的对角线加 1

以下解决方案的时间复杂度为 O(n log n)，辅助空间为 O(n)，其中 n 是 树中的节点数：

// print the diagonal elements of given binary tree
public void printDiagonalRecursive() {
  // map of diagonals
  Map<Integer, List<T>> map = new HashMap<>();
  // Pre-Order traversal of the tree and fill up the map
  printDiagonal(root, 0, map);
  // print the current diagonal
  for (int i = 0; i < map.size(); i++) {
    System.out.println(map.get(i));
  }
}
// recursive Pre-Order traversal of the tree 
// and put the diagonal elements in the map
private void printDiagonal(Node node, 
        int diagonal, Map<Integer, List<T>> map) {
  if (node == null) {
    return;
  }
  // insert the current node in the diagonal
  if (!map.containsKey(diagonal)) {
    map.put(diagonal, new ArrayList<>());
  }
  map.get(diagonal).add(node.element);
  // increase the diagonal by 1 and go to the left sub-tree
  printDiagonal(node.left, diagonal + 1, map);
  // maintain the current diagonal and go 
  // to the right sub-tree
  printDiagonal(node.right, diagonal, map);
}

现在，让我们看看这个问题的另一种解决方案。

Iterative-based solution

解决这个问题也可以 迭代完成。这一次，我们可以使用 Level-Order 遍历并使用 Queue 将对角线的节点排入队列。该解决方案的主要伪代码可以编写如下：

(first diagonal)
Enqueue the root and all its right children 
While the queue is not empty
	Dequeue (let's denote it as A)
	Print A
    (next diagonal)
	If A has a left child then enqueue it 
    (let's denote it as B)
		Continue to enqueue all the right children of B

当将此伪代码放入代码中时，我们得到以下信息：

public void printDiagonalIterative() {
  Queue<Node> queue = new ArrayDeque<>();
  // mark the end of a diagonal via dummy null value
  Node dummy = new Node(null);
  // enqueue all the nodes of the first diagonal
  while (root != null) {
    queue.add(root);
    root = root.right;
  }
  // enqueue the dummy node at the end of each diagonal
  queue.add(dummy);
  // loop while there are more nodes than the dummy
  while (queue.size() != 1) {
    Node front = queue.poll();
    if (front != dummy) {
      // print current node
      System.out.print(front.element + " ");
      // enqueue the nodes of the next diagonal 
      Node node = front.left;
      while (node != null) {
        queue.add(node);
        node = node.right;
      }
    } else {
      // at the end of the current diagonal enqueue the dummy                 
      queue.add(dummy);
      System.out.println();
    }
  }
}

前面的代码运行时间为O(n)，辅助空间为O(n)，其中n是树中的节点。完整的 应用程序称为BinaryTreePrintDiagonal。

Coding challenge 15 – Handling duplicates in BSTs

亚马逊、微软、Flipkart

问题：假设您已经获得了允许重复的 BST。编写一个在处理重复项时支持插入和删除操作的实现。

解决方案：我们知道 BST 的属性声称对于每个节点 n，我们知道 n ≤ n < 的左后代n的右后裔。通常，涉及 BST 的问题不允许重复，因此无法插入重复。但是，如果允许重复，那么我们的约定是将重复插入到左子树中。

但是，面试官可能希望看到一个允许我们将计数与每个节点相关联的实现，如下图所示：

图 13.36 – 在 BST 中处理重复

为了提供这种实现，我们 需要修改经典 BST 的结构，使其支持计数器：

private class Node {
  private T element;
  private int count;
  private Node left;
  private Node right;
  private Node(Node left, Node right, T element) {
    this.element = element;
    this.left = left;
    this.right = right;
    this.count = 1;
  }
}

每次我们创建一个新节点（树中不存在的节点）时，计数器都会等于 1。

当我们插入一个节点时，我们需要区分一个新节点和一个重复节点。如果我们插入一个重复节点，那么我们需要做的就是将该节点的计数器加一，而无需 创建一个新节点。此处列出了插入操作的相关部分：

private Node insert(Node current, T element) {
  if (current == null) {
    return new Node(null, null, element);
  }
  // START: Handle inserting duplicates
  if (element.compareTo(current.element) == 0) {
    current.count++;
    return current;
  }
  // END: Handle inserting duplicates
...
}

删除节点遵循类似的逻辑。如果我们删除一个重复节点，那么我们只需将其计数器减一。如果计数器已经等于 1，那么我们只需删除该节点。相关代码如下：

private Node delete(Node node, T element) {
  if (node == null) {
    return null;
  }
  if (element.compareTo(node.element) < 0) {
    node.left = delete(node.left, element);
  } else if (element.compareTo(node.element) > 0) {
    node.right = delete(node.right, element);
  }
  if (element.compareTo(node.element) == 0) {
    // START: Handle deleting duplicates
    if (node.count > 1) {
      node.count--;
      return node;
    }
    // END: Handle deleting duplicates
    ...
}

完整的 应用程序是，称为BinarySearchTreeDuplicates。此问题的另一个解决方案包括使用哈希表来保持节点的数量。这样，您就不会修改树结构。挑战自己并完成此实施。

Coding challenge 16 – Isomorphism of binary trees

亚马逊、谷歌、微软

问题：假设您已经获得了两棵二叉树。编写一段代码，判断这两个二叉树是否彼此同构。

解决方案：如果您不熟悉术语isomorphic，那么您必须向面试官澄清这一点。这个术语在数学中定义非常明确，但面试官可能不会给出数学解释/演示，而且，如你所知，数学家有自己的语言，很难通过流利和易于理解的英语。此外，在数学中，同构的概念是指任何两个结构，而不仅仅是二叉树。所以，面试官可能会给你一个解释，如下（让我们将树表示为 T1 和 T2）：

定义1：如果T1可以通过多次交换子节点变为T2，则T1和T2是同构的。 T1 和 T2 根本不必是相同的物理形状。

定义 2：T1 和 T2 是同构的，如果您可以将 T1 转换为 T2 并将 T2 转换为 T1 而不会丢失信息。

定义 3：想想两个字符串，AAB 和 XXY。如果A转化为X，B转化为Y，那么AAB就变成了XXY，所以这两个字符串是同构的。因此，如果 T2 是 T1 的结构镜像，则两棵二叉树是同构的。

不管你从面试官那里得到什么定义，我很确定他们都会试图给你一个例子。下图展示了一堆同构二叉树的例子：

图 13.37 – 同构二叉树示例

基于前面的定义和示例，我们可以形成以下算法来确定两个二叉树是否同构：

1. 如果 T1 和 T2 为 null，则 它们是同构的，所以返回 true。
2. 如果 T1 或 T2 是 null，那么它们不是同构的，所以返回 false.
3. 如果 T1.data 不等于 T2.data, 那么它们不是同构的，所以返回 假。
4. 遍历T1的左子树和T2的左子树。
5. Traverse the right sub-tree of T1 and the right sub-tree of T2:

   一个。如果T1和T2的结构相同，则返回true。

   湾。如果 T1 和 T2 的结构不相同，那么我们检查一棵树（或子树）是否在镜像另一棵树树（子树），

6. 遍历T1的左子树和T2的右子树。
7. Traverse the right sub-tree of T1 and the left sub-tree of T2:

   一个。如果结构被镜像，则返回 true;否则，返回 false。

将此算法放入代码中，如下：

private boolean isIsomorphic(Node treeOne, Node treeTwo) {
  // step 1
  if (treeOne == null && treeTwo == null) {
    return true;
  }
  // step 2
  if ((treeOne == null || treeTwo == null)) {
    return false;
  }
  // step 3
  if (!treeOne.element.equals(treeTwo.element)) {
    return false;
  }
  // steps 4, 5, 6 and 7
  return (isIsomorphic(treeOne.left, treeTwo.right)
    && isIsomorphic(treeOne.right, treeTwo.left)
    || isIsomorphic(treeOne.left, treeTwo.left)
    && isIsomorphic(treeOne.right, treeTwo.right));
}
.

完整的应用程序是，称为TwoBinaryTreesAreIsomorphic。

Coding challenge 17 – Binary tree right view

亚马逊、谷歌、Adobe、微软，Flipkart

问题：假设您已经获得了一棵二叉树。编写一段代码，打印这棵树的右视图。打印 right view 意味着打印从右侧查看二叉树时可以看到的所有节点。

解决方案：如果您不确定二叉树的正确视图是什么，请向面试官说明这一点。例如，下图突出显示了代表二叉树右视图的节点：

图 13.38 – 二叉树的右视图

因此，如果您位于这棵树的右侧，您将只能看到节点 40、45、44、9 和 2。如果我们考虑 Level-Order traversal (BFS)，我们会获得以下输出：

• 40、47、45、11、3、44、7、 5、9、2

突出显示的节点是代表正确视图的节点。但是，这些节点中的每一个都代表树中每个级别的最右边的节点。这意味着我们可以调整 BFS 算法并打印每个级别的最后一个节点。

这是一个 O(n) 复杂度时间算法，带有辅助 O(n) 空间（由队列表示），其中 n 是树中的节点数：

private void printRightViewIterative(Node root) {
  if (root == null) {
    return;
  }
  // enqueue root node
  Queue<Node> queue = new ArrayDeque<>();
  queue.add(root);
  Node currentNode;
  while (!queue.isEmpty()) {
    // number of nodes in the current level is the queue size
    int size = queue.size();
    int i = 0;
    // traverse each node of the current level and enqueue its
    // non-empty left and right child
    while (i < size) {
      i++;
      currentNode = queue.poll();
      // if this is last node of current level just print it
      if (i == size) {
        System.out.print(currentNode.element + " ");
      }
      if (currentNode.left != null) {
        queue.add(currentNode.left);
      }
      if (currentNode.right != null) {
        queue.add(currentNode.right);
      }
    }
  }
}

在这里，我们也可以实现递归解决方案。

这是一个 O(n) 复杂度时间算法，具有辅助 O(n) 空间（由映射表示），其中 n 是树中的节点数。您可以在 本书 BinaryTreeRightView 应用程序。挑战自己，实现二叉树的左视图。

Coding challenge 18 – kth largest element

Google、Flipkart

问题：假设您已获得了 BST。编写一段代码，在不更改 BST 的情况下打印 kth 最大元素。

解决方案：让我们考虑以下 BST：

图 13.39 – BST 中的第 k 个最大元素

对于 k=1，我们可以看到 56 是第一个最大的元素。对于 k=2，我们可以看到 55 是第二大元素，以此类推。

蛮力解决方案非常简单，将在 O(n) 时间内运行，其中 n 是树中的节点数。我们所要做的就是提取一个数组并将其放入树的有序遍历 (left sub-tree | right sub-tree | root) 中：45, 47 , 50, 52, 54, 55, 56。一旦我们这样做了，我们可以找到 kth 元素数组[n-k]。例如，对于 k=3，第三个元素是 array[7-3] = 数组[4]=54。如果您愿意，您可以挑战自己并提供此实现。

但是，另一种在 O(k+h) 复杂度时间内运行的方法，其中 h 是 BST 的高度，可以基于 Reverse-In-Order 遍历来编写 < strong class="bold">(right sub-tree | left sub-tree | root)，它为我们提供了降序排列的元素：56、55、54、52、50、47、45。

代码不言自明（c 变量计算访问的节点）：

public void kthLargest(int k) {
  kthLargest(root, k);
}
private int c;
private void kthLargest(Node root, int k) {
  if (root == null || c >= k) {
    return;
  }
  kthLargest(root.right, k);
  c++;
  // we found the kth largest value
  if (c == k) {
    System.out.println(root.element);
  }
  kthLargest(root.left, k);
}

完整的应用程序称为BinarySearchTreeKthLargestElement。

Coding challenge 19 – Mirror binary tree

亚马逊、谷歌、Adobe、微软

问题：假设您已经 给出了一棵二叉树。编写一段代码来构建这棵树的镜像。

解决方案：镜像树如下（右侧的树是左侧树的镜像版本）：

图 13.40 – 给定树和镜像树

因此，镜像树就像给定树的水平翻转。要创建树的镜像，我们必须决定是将镜像树作为新树返回还是将给定树镜像到位。

Mirroring the given tree in a new tree

可以通过遵循以下步骤的递归算法将 镜像作为新树返回：

图 13.41 - 递归算法

在代码方面，我们有以下内容：

private Node mirrorTreeInTree(Node root) {
  if (root == null) {
    return null;
  }
  Node node = new Node(root.element);
  node.left = mirrorTreeInTree(root.right);
  node.right = mirrorTreeInTree(root.left);
  return node;
}

现在，让我们尝试将给定的树镜像到位。

Mirroring the given tree in place

镜像给定的 树也可以通过递归来完成。这一次，算法遵循以下步骤：

1. 镜像给定树的左子树。
2. 镜像给定树的右子树。
3. 交换左右子树（交换它们的指针）。

在代码方面，我们有以下内容：

private void mirrorTreeInPlace(Node node) {
  if (node == null) {
    return;
  }
  Node auxNode;
  mirrorTreeInPlace(node.left);
  mirrorTreeInPlace(node.right);
  auxNode = node.left;
  node.left = node.right;
  node.right = auxNode;
}

完整的 应用程序称为MirrorBinaryTree。

Coding challenge 20 – Spiral-level order traversal of a binary tree

亚马逊、谷歌、微软

问题：假设您已经获得了一棵二叉树。编写一段代码，打印此二叉树的螺旋级遍历。更准确地说，应该从左到右打印第 1 层的所有节点，然后从右到左打印第 2 层的所有节点，然后从左到右打印第 3 层的所有节点，以此类推上。因此，奇数级别应该从左到右打印，偶数级别应该从右到左打印。

解决方案：螺旋级遍历可以有两种形式，如下：

• 奇数级别应该从左到右打印，偶数级别应该从右到左打印。
• 奇数级别应该从右到左打印，偶数级别应该从左到右打印。

下图表示这些语句：

图 13.42 – 螺旋顺序遍历

因此，在左侧 一侧，我们得到 50、12、45、12、3、65、70、24 和 41。另一方面，在右侧- 手边，我们得到 50、45、12、70、65、3、12、41 和 24。

Recursive approach

让我们尝试从上图的左侧实现螺旋顺序遍历。请注意，奇数级别应该从左到右打印，而偶数级别应该以相反的顺序打印。基本上，我们需要通过翻转偶数级别的方向来调整众所周知的 Level-Order 遍历。这意味着我们可以使用布尔变量来交替打印顺序。所以，如果布尔变量是true（或1），那么我们从左到右打印当前级别；否则，我们从右到左打印它。在每次迭代（级别）中，我们翻转布尔值。

通过递归应用它可以如下完成：

public void spiralOrderTraversalRecursive() {
  if (root == null) {
    return;
  }
  int level = 1;
  boolean flip = false;
  // as long as printLevel() returns true there 
  // are more levels to print
  while (printLevel(root, level++, flip = !flip)) {
    // there is nothing to do
  };
}
// print all nodes of a given level 
private boolean printLevel(Node root, 
      int level, boolean flip) {
  if (root == null) {
    return false;
  }
  if (level == 1) {
    System.out.print(root.element + " ");
    return true;
  }
  if (flip) {
    // process left child before right child
    boolean left = printLevel(root.left, level - 1, flip);
    boolean right = printLevel(root.right, level - 1, flip);
    return left || right;
  } else {
    // process right child before left child
    boolean right = printLevel(root.right, level - 1, flip);
    boolean left = printLevel(root.left, level - 1, flip);
    return right || left;
  }
}

这段代码在 O(n2) 时间内运行， 效率很低。我们可以更有效地做到这一点吗？是的——我们可以通过迭代方法在 O(n) 时间内用额外的空间 O(n) 完成。

Iterative approach

让我们尝试从给定图表的右侧实现螺旋顺序遍历。这次我们将通过迭代方法来做到这一点。主要是，我们可以使用两个堆栈（Stack）或一个双端队列（Deque）。让我们学习如何通过两个堆栈来做到这一点。

使用两个堆栈的主要思想非常简单：我们使用一个堆栈打印从左到右的节点，另一个堆栈打印从右到左的节点。在每次迭代（或级别）中，我们在其中一个堆栈中都有相应的节点。当我们从堆栈打印节点时，我们将下一级的节点推入另一个堆栈。

以下 代码将这些语句转换为代码形式：

private void printSpiralTwoStacks(Node node) {
  if (node == null) {
    return;
  }
  // create two stacks to store alternate levels         
  Stack<Node> rl = new Stack<>(); // right to left         
  Stack<Node> lr = new Stack<>(); // left to right 
  // Push first level to first stack 'rl' 
  rl.push(node);
  // print while any of the stacks has nodes 
  while (!rl.empty() || !lr.empty()) {
    // print nodes of the current level from 'rl' 
    // and push nodes of next level to 'lr'
    while (!rl.empty()) {
      Node temp = rl.peek();
      rl.pop();
      System.out.print(temp.element + " ");
      if (temp.right != null) {
        lr.push(temp.right);
      }
      if (temp.left != null) {
        lr.push(temp.left);
      }
    }
    // print nodes of the current level from 'lr' 
    // and push nodes of next level to 'rl'
    while (!lr.empty()) {
      Node temp = lr.peek();
      lr.pop();
      System.out.print(temp.element + " ");
      if (temp.left != null) {
        rl.push(temp.left);
      }
      if (temp.right != null) {
        rl.push(temp.right);
      }
    }
  }
}

完整的应用程序被称为BinaryTreeSpiralTraversal。在这个应用程序中，您还可以找到基于 Deque 的实现。

Coding challenge 21 – Nodes at a distance k from leafs

亚马逊、谷歌、微软、 Flipkart

问题：考虑 给你一个整数的二叉树和一个整数 k 。编写一段代码，打印距离叶节点 k 的所有节点。

解决方案：我们可以直观地认为距离叶子k意味着k 叶子上方的水平。但是为了澄清任何疑问，让我们遵循经典方法并尝试可视化一个示例。下图表示一棵二叉树；突出显示的节点（40、47 和 11）表示距离叶节点 k=2 的节点：

图 13.43 – 距离叶节点 k=2 的节点

从上图中，我们可以得出以下观察结果：

• 节点 40 与叶 44 的距离为 2。
• 节点 47 与叶子 9 和叶子 5 的距离为 2。
• 节点 11 与叶子 2 的距离为 2。

如果我们查看每个级别，那么我们可以看到以下内容：

• 距叶节点距离为 1 的节点为 3、11、7 和 45。
• 距叶节点距离为 2 的节点为 11、47 和 40。
• 离叶节点距离为 3 的节点是 40 和 47。
• 距离叶节点 4 的节点是 40 。

所以，根节点离叶子的距离最大，而 k 大于层数是没有意义的；也就是说，1. 如果我们从根开始，沿着树向下直到找到叶子，那么生成的路径应该包含一个距离 k 从那片叶子。

例如，可能的路径是 40（根）、47、11、7 和 2（叶）。如果 k=2，则节点 11 与叶的距离为 2。另一个可能的路径是 40（根）、47、11 和 5（叶）。如果 k=2，则节点 47 与叶的距离为 2。另一条路径是 40（根）、47、3 和 9（叶）。如果 k=2，则节点 47 与叶的距离为 2。我们已经找到了这个节点；因此，我们现在必须注意并删除重复项。

如此列出的路径 far 表明存在树的 Pre-Order 遍历 (root | left sub-tree | right sub-树）。在遍历过程中，我们必须跟踪当前路径。换句话说，构造的路径是由Pre-Order遍历中当前节点的祖先组成的。当我们找到一个叶子节点时，我们必须打印距离该叶子 k 的祖先。

为了消除重复，我们可以使用 Set（我们将其表示为 nodesAtDist），如下代码所示：

private void leafDistance(Node node, 
    List<Node> pathToLeaf, Set<Node> nodesAtDist, int dist) {
  if (node == null) {
    return;
  }
  // for each leaf node, store the node at distance 'dist'
  if (isLeaf(node) && pathToLeaf.size() >= dist) {
    nodesAtDist.add(pathToLeaf.get(pathToLeaf.size() - dist));
    return;
  }
  // add the current node into the current path        
  pathToLeaf.add(node);
  // go  to left and right subtree via recursion
  leafDistance(node.left, pathToLeaf, nodesAtDist, dist);
  leafDistance(node.right, pathToLeaf, nodesAtDist, dist);
  // remove the current node from the current path       
  pathToLeaf.remove(node);
}
private boolean isLeaf(Node node) {
  return (node.left == null && node.right == null);
}

上述代码运行在O(n)时间复杂度和辅助空间O(n)，其中n是节点数在树上。完整的 应用程序称为BinaryTreeDistanceFromLeaf。

Coding challenge 22 – Pair for a given sum

亚马逊、谷歌、Adobe、微软，Flipkart

问题：假设您已 获得了 BST 和总和。如果有一对具有此总和的节点，则编写一个返回 true 的代码片段。

解决方案：让我们考虑下图中显示的 BST 和 sum=74：

图片 13.44 – sum=74 的对包含节点 6 和 68

因此，对于 sum=74，我们可以找到 (6, 68) 对。如果 sum=89，则该对为 (43, 46)。如果 sum=99，则该对为 (50, 49)。形成对的节点可以来自相同的子树或不同的子树，也可以包括根节点和叶节点。

此问题的一种解决方案依赖于 散列 和递归。主要是，我们使用中序遍历（left sub-tree | root | 右子树），我们将每个节点的元素插入到一个集合中（例如，插入到一个HashSet）。此外，在将当前节点插入集合之前，我们检查（给定的总和 - 当前节点的元素）是否存在于集合中。如果是，那么我们找到了一对，所以我们停止该过程并返回 true。否则，我们将当前节点插入到集合中并继续这个过程，直到找到一对，或者遍历完成。

此处列出了此代码：

public boolean findPairSum(int sum) {
  return findPairSum(root, sum, new HashSet());
}
private static boolean findPairSum(Node node, 
        int sum, Set<Integer> set) {
  // base case
  if (node == null) {
    return false;
  }
  // find the pair in the left subtree 
  if (findPairSum(node.left, sum, set)) {
    return true;
  }
  // if pair is formed with current node then print the pair      
  if (set.contains(sum - node.element)) {
    System.out.print("Pair (" + (sum - node.element) + ", "
      + node.element + ") = " + sum);
    return true;
  } else {
    set.add(node.element);
  }
  // find the pair in the right subtree 
  return findPairSum(node.right, sum, set);
}

此代码的运行时间为 O(n)，辅助空间为 O(n)。完整的应用程序 称为BinarySearchTreeSum。

您可能想考虑和挑战自己的另一个解决方案 始于这样一个事实，即当使用 In-Order 遍历进行遍历时，BST 会按排序顺序输出节点。这意味着如果我们扫描 BST 并将输出存储在一个数组中，那么问题与在数组中找到给定和的对完全相同。但是这个解决方案需要对所有节点进行两次遍历和一个 O(n) 的辅助空间。

另一种方法从 BST 属性开始： n ≤ n left descendants of n ≤ n < n的右后裔。换句话说，树中的最小节点是最左边的节点（在我们的例子中是 6），而树中的最大节点是最右边的节点（在我们的例子中是 71）。现在，考虑树的两次遍历：

• 前序遍历（最左边的节点是第一个访问的节点）
• 逆序遍历（最右边的节点是第一个访问的节点）

现在，让我们计算 (minimum + maximum) 表达式：

• if (最小值 + 最大值) sum，然后转到下一个 minimum（前向有序遍历返回的下一个节点）。
• if (最小 + 最大) > sum，然后进入下一个maximum（逆序遍历返回的下一个节点）。
• 如果 (minimum + maximum) = sum，则返回 true。

这里的主要问题是我们需要管理这两个遍历。一种方法可以依赖于两个堆栈。在一个堆栈中，我们存储正序遍历的输出，而在另一个堆栈中，我们存储逆序遍历的输出。当我们到达 minimum（最左边）和 maximum（最右边）节点时，我们必须弹出栈顶并执行针对给定的 sum 进行相等性检查。

此相等检查通过前面的检查之一（由前面的三个项目符号给出）并解释如下：

• if (最小值 + 最大值) sum，然后我们通过 Forward In-Order 遍历到弹出节点的右子树。这就是我们如何找到下一个最大元素的方法。
• if (最小 + 最大) > sum，然后我们通过 Reverse In-Order 遍历到弹出节点的左子树。这就是我们如何找到下一个最小元素的方法。
• 如果 (minimum + maximum) = sum，那么我们找到了一对验证给定 总和。

只要前向有序和反向有序遍历不满足，该算法就被应用为。让我们看看代码：

public boolean findPairSumTwoStacks(int sum) {
  return findPairSumTwoStacks(root, sum);
}
private static boolean findPairSumTwoStacks(
              Node node, int sum) {
  Stack<Node> fio = new Stack<>(); // fio - Forward In-Order
  Stack<Node> rio = new Stack<>(); // rio - Reverse In-Order
  Node minNode = node;
  Node maxNode = node;
  while (!fio.isEmpty() || !rio.isEmpty()
           || minNode != null || maxNode != null) {
    if (minNode != null || maxNode != null) {
      if (minNode != null) {
        fio.push(minNode);
        minNode = minNode.left;
      }
      if (maxNode != null) {
        rio.push(maxNode);
        maxNode = maxNode.right;
      }
    } else {
      int elem1 = fio.peek().element;
      int elem2 = rio.peek().element;
      if (fio.peek() == rio.peek()) {
        break;
      }
      if ((elem1 + elem2) == sum) {
        System.out.print("\nPair (" + elem1 + ", " 
             + elem2 + ") = " + sum);
        return true;
      }
      if ((elem1 + elem2) < sum) {
        minNode = fio.pop();
        minNode = minNode.right;
      } else {
        maxNode = rio.pop();
        maxNode = maxNode.left;
      }
    }
  }
  return false;
}

此代码的运行时间 为 O(n)，辅助空间为 O(n)。完整的 应用程序称为 BinarySearchTreeSum。

Coding challenge 23 – Vertical sums in a binary tree

亚马逊、谷歌、Flipkart

问题：假设您已经 获得了一棵二叉树。编写一段代码来计算这个二叉树的垂直和。

解决方案：为了清楚地了解这个问题，绘制一个有意义的图表非常重要。使用带正方形的笔记本（数学笔记本）会非常有用。这很有用，因为您必须在节点之间绘制 45 度的边；否则，您可能无法正确看到节点的垂直轴。通常，当我们绘制二叉树时，我们并不关心节点之间的角度，但在这种情况下，这是理解问题并找到解决方案的重要方面。

下图是二叉树的示意图。它显示了一些有用的地标，将引导我们找到解决方案：

图 13.45 – 二叉树中的垂直和

如果我们从左侧到右侧扫描树，我们可以识别出 7 个垂直轴，它们的和分别为 5、7、16、35、54、44 和 6。在图的顶部，我们'已经添加了每个节点到根节点的水平距离。如果我们认为根节点的距离为 0，那么我们可以通过将 1 分别减小、增加为 -3、-2、-1、0（根）、1、2、3。

每个轴都由其与根的距离唯一标识，每个轴都包含我们必须求和的节点。如果我们把一个轴的唯一距离作为一个键，把这个轴上的节点之和作为一个值，那么我们可以直观地认为这个问题可以通过hashing来解决（如果你不熟悉哈希的概念，那么请看一下第6章，面向对象编程，哈希表问题）。在 Java 中，我们可以通过内置的 HashMap 实现来使用哈希，因此无需从头开始编写哈希实现。

但是我们怎样才能填满这张地图呢？ 很明显，我们必须在填充地图时遍历树。我们可以从根开始，将映射的键添加为 0（0 对应于包含根的轴）和值作为根（21）。接下来，我们可以通过将与根的距离减少 1 来使用递归到根的左轴。我们也可以通过将与根的距离增加 1 来使用递归通过根的右轴. 在每个节点，我们更新映射中与标识当前轴的键对应的值。所以，如果我们递归地遵循路径 root|左子树|右子树，那么我们使用二叉树的Pre-Order遍历。

最后，我们的地图应该包含以下键值对：(-3, 5), (-2, 7), (-1, 16), (0, 35), (1, 54), (2 , 44) 和 (3, 6)。

将此算法放入代码中会产生以下结果（map 包含垂直总和）：

private void verticalSum(Node root, 
        Map<Integer, Integer> map, int dist) {
  if (root == null) {
    return;
  }
  if (!map.containsKey(dist)) {
    map.put(dist, 0);
  }
  
  map.put(dist, map.get(dist) + root.element);        
  // or in functional-style
  /*
  BiFunction <Integer, Integer, Integer> distFunction
    = (distOld, distNew) -> distOld + distNew;
  map.merge(dist, root.element, distFunction);
  */
  // decrease horizontal distance by 1 and go to left
  verticalSum(root.left, map, dist - 1);
  // increase horizontal distance by 1 and go to right
  verticalSum(root.right, map, dist + 1);
}

上述代码运行时间为 O(n log n)，辅助空间为 O(n)，其中 n 是树的节点总数。添加到地图的复杂度时间为 O(log n)，由于我们对树的每个节点都进行了添加，这意味着我们得到了 O(n log n)。对于面试，这里提供的解决方案应该足够了。但是，您可以通过使用额外的双向链表来挑战自己并将时间复杂度降低到 O(n)。主要是需要 将每个垂直总和存储在链表的一个节点中。首先，将包含根的轴对应的垂直和添加到链表中。那么，链表的node.next和node.prev应该存储从左到右轴的垂直和根轴的右侧。最后，在遍历树时，依靠递归更新链表。

完整的 应用程序称为BinaryTreeVerticalSum。

Coding challenge 23 – Converting a max heap into a min heap

亚马逊、谷歌、Adobe、微软，Flipkart

问题：考虑你得到了一个代表最小二叉堆的数组。编写一段代码，在线性时间内将给定的 Min Binary Heap 转换为 Max Binary Heap，无需额外空间。

Solution：这个问题的解决方案受到Heap Sort算法的启发（这个算法在第 14 章，排序和搜索）。

最初，这个问题可能听起来很复杂，但经过几分钟的思考，您可能会得出结论，可以将问题简化为从未排序的数组构建 Max Binary Heap。因此，给定数组是否是最小二进制堆这一事实并不重要。我们可以通过以下两个步骤从任何数组（已排序或未排序）构建所需的最大二进制堆：

1. 从给定数组的最右边、最底部的节点（最后一个内部节点）开始。
2. Heapify 所有节点通过自底向上技术。

代码不言自明：

public static void convertToMinHeap(int[] maxHeap) {
  // build heap from last node to all 
  // the way up to the root node
  int p = (maxHeap.length - 2) / 2;
  while (p >= 0) {
    heapifyMin(maxHeap, p--, maxHeap.length);
  }
}
// heapify the node at index p and its two direct children    
private static void heapifyMin(int[] maxHeap,
      int p, int size) {
  // get left and right child of node at index p
  int left = leftChild(p);
  int right = rightChild(p);
  int smallest = p;
  // compare maxHeap[p] with its left and 
  // right child and find the smallest value
  if ((left < size) && (maxHeap[left] < maxHeap[p])) {
    smallest = left;
  }
  if ((right < size) 
      && (maxHeap[right] < maxHeap[smallest]))  {
    smallest = right;
  }
  // swap 'smallest' with 'p' and heapify
  if (smallest != p) {
    swap(maxHeap, p, smallest);
    heapifyMin(maxHeap, smallest, size);
  }
}
/* Helper methods */
private static int leftChild(int parentIndex) {
  return (2 * parentIndex + 1);
}
private static int rightChild(int parentIndex) {
  return (2 * parentIndex + 2);
}
// utility function to swap two indices in the array
private static void swap(int heap[], int i, int j) {
  int aux = heap[i];
  heap[i] = heap[j];
  heap[j] = aux;
}

此代码的运行时间为 O(n)，不需要 额外空间。完整的应用程序称为MaxHeapToMinHeap。它还包含将最小二进制堆转换为最大二进制堆。

Coding challenge 24 – Finding out whether a binary tree is symmetric

亚马逊、谷歌、Adobe、微软，Flipkart

问题：假设您已经给定了一棵二叉树。编写一段代码，如果此二叉树是对称的，则返回 true（是否为自身的镜像；左子树和右子树是各自的镜像）其他）。

解决方案：首先，我们来看一张包含对称和非对称二叉树的图。标记为 (a)、(b) 和 (d) 的二叉树是不对称的，而标记为 (c)、(e) 和 (f) 的二叉树是对称的。请注意，如果结构和数据都是对称的，则二叉树是对称的：

图 13.46 – 对称和非对称二叉树示例

我们可以把这个问题想象成镜像 root.left 并检查它是否与 root.right 相同。如果它们相同，则二叉树是对称的。但是，我们也可以通过三个条件来表达两棵二叉树的对称性，如下所示（理解这些条件的最简单方法是分别取它们并将它们传递给上图所示的样本）：

1. 根节点的元素是相同的。
2. 左树的左子树和右树的右子树必须是镜像。
3. 左树的右子树和右树的左子树必须是镜像。

我认为我们有足够的经验来认识到这些条件可以通过递归来实现，如下：

private boolean isSymmetricRecursive(
      Node leftNode, Node rightNode) {
  boolean result = false;
  // empty trees are symmetric
  if (leftNode == null && rightNode == null) {
    result = true;
  }
  // conditions 1, 2, and 3 from above
  if (leftNode != null && rightNode != null) {
    result = (leftNode.element.equals(rightNode.element))
      && isSymmetricRecursive(leftNode.left, rightNode.right)
      && isSymmetricRecursive(leftNode.right, rightNode.left);
  }
  return result;
}

这段代码的时间复杂度是 O(n) 加上 O(h) 额外空间，其中 h 是树的高度。迭代实现怎么样？我们可以通过队列提供迭代实现。 以下代码是对这种方法的最佳解释：

public boolean isSymmetricIterative() {        
  boolean result = false;
  Queue<Node> queue = new LinkedList<>();
  queue.offer(root.left);
  queue.offer(root.right);
  while (!queue.isEmpty()) {
    Node left = queue.poll();
    Node right = queue.poll();
    if (left == null && right == null) {
      result = true;
    } else if (left == null || right == null 
                || left.element != right.element) {
      result = false;
      break;
    } else {
      queue.offer(left.left);
      queue.offer(right.right);
      queue.offer(left.right);
      queue.offer(right.left);
    }
  }
  return result;
}

这段代码的时间 复杂度为 O(n)，额外空间为 O(h)，其中 h 是树。完整的 应用程序称为 IsSymmetricBinaryTree。

Coding challenge 25 – Connecting n ropes at the minimum cost

亚马逊、谷歌、Adobe、微软，Flipkart

问题：假设您已经 获得了一个包含 n 绳索，我们需要将所有这些绳索连接到一根绳索上。考虑连接两条绳索的成本等于它们的长度之和。编写一段代码，以最低成本将所有绳索连接到一条绳索。

解决方案：假设我们有四根绳子，长度分别为 1、3、4 和 6。让我们先连接最短的两根绳子。这意味着我们需要连接绳索 1 和 3，其成本为 1+3=4。继续使用相同的逻辑，接下来的两条绳索是 4 （我们刚刚获得的），长度为 4。成本是 4+4=8，所以总成本是 4+8=12。我们剩下两条绳子，长度分别为 8 和 6。连接它们的成本是 8+6=14。因此，总成本和最终成本为 12+14=26。

现在，让我们尝试另一种策略。我们先把最长的两条绳子连接起来。这意味着我们需要连接绳索 4 和 6，其成本为 4+6=10。继续使用相同的逻辑，接下来的两条绳索长度为 10（我们刚刚获得的那条）和 3。成本是 10+3=13，所以总成本是 10+13=23。我们剩下两条绳子，长度分别为 13 和 1。连接它们的成本是 13+1=14。因此，总成本和最终成本为 23+14=37。

由于 37>26，很明显第一种方法优于第二种方法。但是有什么问题呢？好吧，如果您还没有注意到，连接的绳索的长度首先出现在其余的连接中。例如，当我们连接绳索 1 和 3 时，我们写为 1+3=4。所以，4 是到目前为止的总成本。接下来我们加上4+4=8，所以新的总成本就是之前的总成本+8，也就是4+8，但是4是从1+3得到的，所以1+3又出现了。最后，我们连接 8+6=14。新的总成本是之前的成本+14，也就是12+14，但是12是从4+8得到的，4是从1+3得到的，所以1+3又出现了。

分析前面的语句，我们可以得出这样的结论：如果重复添加的绳子最小，然后是第二小，以此类推，我们可以获得连接所有绳子的最小成本。换句话说，我们可以这样想算法：

1. 按绳索的长度降序排列。
2. 连接前两条绳索并更新部分最低成本。
3. 将前两条绳索替换为生成的绳索。
4. 从 step 1 重复，直到剩下一根绳子（连接所有绳子的结果）。

实现这个算法后，我们应该得到最终的最小代价。如果我们尝试通过快速排序或合并排序等排序算法来实现该算法，那么结果将在 O(n2 log n) 时间内执行。正如您从 第 7 章, Big O Analysis of Algorithms，这些排序算法的执行时间为 O(n log n)，但每次连接两根绳索时，我们都必须对数组进行排序。

我们可以做得更好吗？我们可以！在任何时候，我们只需要长度最小的两条绳子；我们不关心数组的其余部分。换句话说，我们需要一个能够让我们有效访问最小元素的数据结构。因此，答案是最小二进制堆。在最小二叉堆中添加和删除是一个 O(log n) 复杂度时间操作。其算法可以表示如下：

1. 从绳索长度数组 (O(log n)) 创建最小二进制堆。
2. 轮询最小二叉堆的根，这将为我们提供最小的绳索 (O(log n))。
3. 再次轮询根，这将为我们提供第二小的绳索 (O(log n))。
4. 连接两条绳索（总结它们的长度）并将结果放回最小二进制堆。
5. 从 step 2 重复，直到剩下一根绳子（连接所有绳子的结果）。

因此，在 O(n log n) 复杂度时间内执行的算法如下：

public int minimumCost(int[] ropeLength) {
  if (ropeLength == null) {
    return -1;
  }
  // add the lengths of the ropes to the heap
  for (int i = 0; i < ropeLength.length; i++) {           
    add(ropeLength[i]);
  }
  int totalLength = 0;
  while (size() > 1) {         
    int l1 = poll();
    int l2 = poll();
    totalLength += (l1 + l2);
    add(l1 + l2);
  }
  return totalLength;
}

完整的 应用程序称为HeapConnectRopes。

从一开始，你就应该知道，以下话题在技术面试中很少会遇到。首先，让我将这些主题列举为一个非详尽的列表：

• AVL 树（本书附带的代码中提供了简要说明和实现）
• 红黑树（本书附带的代码中提供了简要描述和实现）
• Dijkstra 算法
• Rabin-Karp 子串搜索
• 贝尔曼福特算法
• Floyd-Warshall 算法
• 区间树
• 最小生成树
• B树
• 二分图
• 图形着色
• P、NP 和 NP 完全
• 组合和概率
• 常用表达
• 一个*

如果你已经掌握了本书所涉及的所有问题，那么我强烈建议你通过研究上述主题来继续学习。如果您不这样做，那么请将所有问题视为比这些主题具有更高优先级。

此处概述的大多数主题可能会或可能不会在面试中被问到。它们代表了你知道或不知道的复杂算法——仅仅因为你能够重现一个著名的算法，面试官就无法真正了解你的逻辑和思维能力。面试官希望看到你有能力利用你的知识。这些算法并没有揭示你解决以前从未见过的问题的能力。很明显，您无法凭直觉理解如此复杂的算法，因此您的足迹几乎是 微不足道的。如果您不了解这些算法，请不要担心！它们不会让你看起来更聪明或更愚蠢！此外，由于它们很复杂，因此需要大量时间来实施，而且在面试中，时间是有限的。

但是，多学习也无妨！这是一个规则，所以如果你有时间，那么也可以看看这些高级主题。

这是本书最难的章节之一，也是任何技术面试的必读。树和图表是如此广泛、精彩和具有挑战性的主题，整本书都专门讨论它们。但是，当您必须准备面试时，您没有时间学习大量书籍并深入研究每个主题。这正是本章的魔力所在：本章（就像整本书一样）完全专注于您必须实现目标的事实：在技术面试中取得成功。

换句话说，本章包含了技术面试中可能遇到的最流行的树和图问题，以及有意义的数字、全面的解释和清晰干净的代码。

在下一章中，我们将解决与排序和搜索相关的问题。