树的题目太多了，先总结一下树的遍历方式。按照根节点的遍历顺序。可以分为前序、中序、后序。前序遍历，即根--左--右的顺序。中序遍历，左--根--右。后续遍历，左--右--根。 用递
树的题目太多了，先总结一下树的遍历方式。 按照根节点的遍历顺序。可以分为前序、中序、后序。 前序遍历，即根-->左-->右的顺序。 中序遍历，左-->根-->右。 后续遍历，左-->右-->根。
用递归实现非常简单: 下面是一个前序遍历，核心部分preorder实现了前序遍历。
class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def preorder(root): nonlocal res res.append(root.val) if root.left: preorder(root.left) if root.right: preorder(root.right) if not root: return [] res = [] preorder(root) return res只要改一下访问顺序，就得到中序遍历：
class Solution: def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def inorder(root): nonlocal res if root.left: inorder(root.left) res.append(root.val) if root.right: inorder(root.right) if not root: return [] res = [] inorder(root) return res同样可以得到后序遍历：
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def postorder(root): nonlocal res if root.left: postorder(root.left) if root.right: postorder(root.right) res.append(root.val) if not root: return [] res = [] postorder(root) return res除了这3种遍历，还有一种层序遍历：每次遍历访问一层节点。 可以用队列来实现：
class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] queue = [root] res = [] while queue: sub_list = [] for i in range(len(queue)): t = queue.pop(0) sub_list.append(t.val) if t.left: queue.append(t.left) if t.right: queue.append(t.right) res.append(sub_list) return res剩下的和树相关的题，大多可以用递归实现。（因为树就是一种递归结构） 有很多与二叉搜索树有关。二叉搜索树（BST）是一种特殊的二叉树，也叫二叉排序树，满足左<根<右的特点。处理BST时要利用这个性质。
二叉搜索树（BST），它或者是一棵空树，或者是具有下列性质的 二叉树 ： 若它的左子树不空，则左子树上所有结点的值均小于它的 根结点 的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为 二叉排序树 。