📄️ 13.1 Data Structure Introduction
As an upgraded version of the (single) linked list, the trees we commonly encounter are typically binary trees, where each node has at most two child nodes. Unless otherwise specified, trees are assumed to have no circular structures. LeetCode's default representation of trees is as follows:
📄️ 13.2 Tree Recursion
For simple recursion problems, some LeetCode experts prefer to write one-line code, solving problems with a single line. While we will showcase such solutions, beginners are still advised to use multi-line if-else statements.
📄️ 13.3 Level Order Traversal
We can use Breadth-First Search (BFS) for level order traversal. Note that it is unnecessary to use two queues to separately store the current layer's nodes and the next layer's nodes. At the beginning of each layer's traversal, the number of nodes in the current queue equals the number of nodes in the current layer. By controlling the traversal to only process that many nodes, we ensure that the traversal covers only the current layer.
📄️ 13.4 Preorder, Inorder, and Postorder Traversals
Preorder traversal, inorder traversal, and postorder traversal are three ways to traverse a binary tree using Depth-First Search (DFS). They differ only in the order of node visits, while the rest remains the same. Consider the following binary tree:
📄️ 13.5 Binary Search Tree
A Binary Search Tree (BST) is a special type of binary tree starting from the root, move to the left if the current node's value is greater than the target value, or move to the right if it's smaller. Additionally, since a BST is ordered, an in-order traversal of the tree results in a sorted array.
📄️ 13.6 Trie
A Trie is a tree-like data structure used to determine whether a string exists or whether it has a specific prefix.
📄️ 13.7 Exercises
Basic Difficulty