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 的一种特例。