Coding interview 的 Tree cheatsheet

Introduction

Tree 是一种常用的抽象数据结构，用来表示层级结构的一组节点。树中的每个节点可以连接多个子节点，但除 root 节点外，每个节点必须且只能有一个 parent。

Tree 是一个无向、连通、无环图。没有 cycles/loops。每个节点都可以视作其子树的 root，因此 recursion 是树遍历中非常常用的技巧。

面试中通常会考 binary tree，而不是 ternary tree（3 个孩子）或 N-ary tree（N 个孩子）。本页主要覆盖 binary tree 以及 binary search tree（BST），它是 binary tree 的一种特例。

Trees 常用于表达层级数据，比如 file system、JSON 和 HTML 文档。也可以看看 Trie，它是用于高效存储与检索字符串的高级树结构。

Learning resources

• Videos
  • Trees, University of California San Diego
  • A Brief Guide to Binary Search Trees (slides), Samuel Albanie, University of Cambridge
  • A Brief Guide to Red-Black Trees (slides), Samuel Albanie, University of Cambridge
  • A Brief Guide to B-trees (slides), Samuel Albanie, University of Cambridge
• Readings
  • How To Not Be Stumped By Trees, basecs
  • Leaf It Up To Binary Trees, basecs
• Additional (only if you have time)
  • The Little AVL Tree That Could, basecs
  • Busying Oneself With B-Trees, basecs
  • Painting Nodes Black With Red-Black Trees, basecs

Common terms you need to know

• Neighbor - 一个节点的 parent 或 child
• Ancestor - 沿着 parent 链可达的节点
• Descendant - 该节点子树中的节点
• Degree - 节点的 children 数量
• Degree of a tree - 树中节点的最大 degree
• Distance - 两个节点之间最短路径上的边数
• Level/Depth - 节点到 root 之间路径上的边数
• Width - 某一层的节点数量

Binary tree

Binary 的含义是二，所以 binary tree 中的节点最多只能有两个 children。

Binary tree terms

• Complete binary tree - 除了可能最后一层外，每一层都被完全填满，最后一层的节点尽可能靠左。
• Balanced binary tree - 对任一节点，其左右子树的高度差不超过 1。

Traversals

对于上图的树，各种遍历的结果如下：

• In-order traversal - Left -> Root -> Right
  • Result: 2, 7, 5, 6, 11, 1, 9, 5, 9
• Pre-order traversal - Root -> Left -> Right
  • Result: 1, 7, 2, 6, 5, 11, 9, 9, 5
• Post-order traversal - Left -> Right -> Root
  • Result: 2, 5, 11, 6, 7, 5, 9, 9, 1

注意：仅靠 in-order traversal 不能唯一序列化一棵树，还需要 pre-order 或 post-order 才能确定结构。

Binary search tree (BST)

对 BST 做 in-order traversal 会得到有序序列。

务必熟悉 BST 的性质，以及如何判断一棵二叉树是否是 BST。这个考点比你想象得更常见。

当题目涉及 BST，面试官通常期待你做出快于 O(n) 的解法。

Time complexity

遍历 balanced tree 的 space complexity 是 O(h)，其中 h 为树高；而非常 skewed 的树（几乎退化成 linked list）会是 O(n)。

Things to look out for during interviews

要熟练写出 pre-order、in-order、post-order 的递归遍历。进阶一点，挑战写出 iterative 版本。面试官有时会要求 iterative 解法，尤其是你快速写完递归版本时。

Corner cases

• Empty tree
• Single node
• Two nodes
• Very skewed tree（像 linked list）

Common routines

很多 tree 题会用到下列 routines，尽量熟悉它们：

• Insert value
• Delete value
• Count number of nodes in tree
• Whether a value is in the tree
• Calculate height of the tree
• Binary search tree
  • Determine if it is a binary search tree
  • Get maximum value
  • Get minimum value

Techniques

Use recursion

Recursion 是遍历树的最常见方法。当你发现“子树问题可以解决整体问题”时，优先考虑 recursion。

写 recursion 时，记得处理 base case，通常是节点为 null 的情况。

有些递归函数可能需要返回两个值。

Traversing by level

如果要求按层遍历，使用 breadth-first search。

Summation of nodes

如果题目涉及路径上的节点求和，别忘了节点值可能为负数。

Essential questions

这些是该 topic 必练题。

• Binary Tree
  • Maximum Depth of Binary Tree
  • Invert/Flip Binary Tree
• Binary Search Tree
  • Lowest Common Ancestor of a Binary Search Tree

Recommended practice questions

这些是在掌握基础后推荐练习的题目。

• Binary tree
  • Same Tree
  • Binary Tree Maximum Path Sum
  • Binary Tree Level Order Traversal
  • Lowest Common Ancestor of a Binary Tree
  • Binary Tree Right Side View
  • Subtree of Another Tree
  • Construct Binary Tree from Preorder and Inorder Traversal
  • Serialize and Deserialize Binary Tree
• Binary search tree
  • Validate Binary Search Tree
  • Kth Smallest Element in a BST

Recommended courses