数据结构介绍
作为单链表的升级版，我们通常接触的树都是二叉树 (Binary Tree)，即每个节点最多有两个子节点；且除非题目说明，默认树中不存在循环结构。LeetCode 默认的树表示方法如下：
1 | class TreeNode: |
可以看出，其与链表的主要差别就是多了一个子节点的指针。
树的递归
对于一些简单的递归题，某些 LeetCode 达人喜欢写 one-line code，即用一行代码解决问题，把 if-else 判断语句压缩成问号冒号的形式。我们也会展示一些这样的代码，但是对于新手，笔者仍然建议您使用 if-else 判断语句。在很多时候，树递归的写法与深度优先搜索的递归写法相同，因此本书不会区分二者。
104. Maximum Depth of Binary Tree
利用递归，我们可以很方便地求得最大深度。
110. Balanced Binary Tree
解法类似于求树的最大深度，但有两个不同的地方：一是我们需要先处理子树的深度再进行比较，二是如果我们在处理子树时发现其已经不平衡了，则可以返回一个 -1，使得所有其长辈节点可以避免多余的判断。
543. Diameter of Binary Tree
同样的，我们可以利用递归来处理树。解题时要注意，在我们处理某个子树时，我们更新的最长直径值和递归返回的值是不同的——待更新的最长直径值是经过该子树根节点的最长直径（即两侧长度）；而函数返回值是以该子树根节点为端点的最长直径值（即一侧长度）。
437. Path Sum III
递归每个节点时，需要分情况考虑：(1) 如果选取该节点加入路径，则之后必须继续加入连续节点，或停止加入节点；(2) 如果不选取该节点加入路径，则对其左右节点进行重新进行考虑。
101. Symmetric Tree
判断一个树是否对称等价于判断左右子树是否对称。笔者一般习惯将判断两个子树是否相等或对称类型的题的解法叫做“四步法”：(1) 如果两个子树都为空指针，则它们相等或对称；(2) 如果两个子树只有一个为空指针，则它们不相等或不对称；(3) 如果两个子树根节点的值不相等，则它们不相等或不对称；(4) 根据相等或对称要求，进行递归处理。
1110. Delete Nodes And Return Forest
这道题最主要需要注意的细节是如果通过递归处理原树，以及需要在什么时候断开指针。同时，为了便于寻找待删除节点，可以建立一个哈希集合方便查找。
层次遍历
我们可以使用广度优先搜索进行层次遍历。注意，不需要使用两个队列来分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。
637. Average of Levels in Binary Tree
利用广度优先搜索，我们可以很方便地求取每层的平均值。
前中后序遍历
前序遍历、中序遍历和后序遍历是三种利用深度优先搜索遍历二叉树的方式。它们是在对节点访问的顺序有一点不同，其它完全相同。
105. Construct Binary Tree from Preorder and Inorder Traversal
前序遍历的第一个节点是 4，意味着 4 是根节点。我们在中序遍历结果里找到 4 这个节点，根据中序遍历的性质可以得出，4 在中序遍历数组位置的左子数组为左子树；4 在中序遍历数组位置的右子数组为右子树。
144. Binary Tree Preorder Traversal
因为递归的本质是栈调用，因此我们可以通过栈来实现前序遍历。注意入栈的顺序。
二叉查找树
二叉查找树 (BST) 是一种特殊的二叉树：对于每个父节点，其左子树中所有节点的值小于等于父结点的值，其右子树中所有节点的值大于等于父结点的值。因此对于一个二叉查找树，我们可以在 O(logn) 的时间内查找一个值是否存在：从根节点开始，若当前节点的值大于查找值则向左下走，若当前节点的值小于查找值则向右下走。同时因为二叉查找树是有序的，对其中序遍历的结果即为排好序的数组。
99. Recover Binary Search Tree
有一个技巧是如果遍历整个序列过程中只出现了一次次序错误，说明就是这两个相邻节点需要被交换；如果出现了两次次序错误，那就需要交换这两个节点。
669. Trim a Binary Search Tree
利用二叉查找树的大小关系，我们可以很容易地利用递归进行树的处理。
字典树
字典树 (Trie) 用于判断字符串是否存在或者是否具有某种字符串前缀。为什么需要用字典树解决这类问题呢？假如我们有一个储存了近万个单词的字典，即使我们使用哈希，在其中搜索一个单词的实际开销也是非常大的，且无法轻易支持搜索单词前缀。然而由于一个英文单词的长度 n 通常在 10 以内，如果我们使用字典树，则可以在 O(n)——近似 O(1) 的时间内完成搜索，且额外开销非常小。
208. Implement Trie (Prefix Tree)
字典树的典型实现方法。
练习
226. Invert Binary Tree
巧用递归，你可以在五行内完成这道题。
617. Merge Two Binary Trees
同样的，利用递归可以轻松搞定。
572. Subtree of Another Tree
子树是对称树的姊妹题，写法也十分类似。
404. Sum of Left Leaves
怎么判断一个节点是不是左节点呢？一种可行的方法是，在辅函数里多传一个参数，表示当前节点是不是父节点的左节点。
513. Find Bottom Left Tree Value
最左下角的节点满足什么条件？针对这种条件，我们该如何找到它？
538. Convert BST to Greater Tree
尝试利用某种遍历方式来解决此题，每个节点只需遍历一次。
235. Lowest Common Ancestor of a Binary Search Tree
利用 BST 的独特性质，这道题可以很轻松完成。
530. Minimum Absolute Difference in BST
还记得我们所说的，对于 BST 应该利用哪种遍历吗？
889. Construct Binary Tree from Preorder and Postorder Traversal
给定任意两种遍历结果，我们都可以重建树的结构。
106. Construct Binary Tree from Inorder and Postorder
给定任意两种遍历结果，我们都可以重建树的结构。
94. Binary Tree Inorder Traversal
因为前中序后遍历是用递归实现的，而递归的底层实现是栈操作，因此我们总能用栈实现。
145. Binary Tree Postorder Traversal
因为前中序后遍历是用递归实现的，而递归的底层实现是栈操作，因此我们总能用栈实现。
236. Lowest Common Ancestor of a Binary Tree
现在不是 BST，而是普通的二叉树了，该怎么办？
109. Convert Sorted List to Binary Search Tree
把排好序的链表变成 BST。为了使得 BST 尽量平衡，我们需要寻找链表的中点。
897. Increasing Order Search Tree
把 BST 压成一个链表，务必考虑清楚指针操作的顺序，否则可能会出现环路。
653. Two Sum IV - Input is a BST
啊哈，这道题可能会把你骗到。
450. Delete Node in a BST
当寻找到待删节点时，你可以分情况考虑——当前节点是叶节点、只有一个子节点和有两个子节点。建议同时回收内存。