树的题目太多了，先总结一下树的遍历方式。
按照根节点的遍历顺序。可以分为前序、中序、后序。
前序遍历，即根–>左–>右的顺序。
中序遍历，左–>根–>右。
后续遍历，左–>右–>根。
用递归实现非常简单:
下面是一个前序遍历，核心部分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），它或者是一棵空树，或者是具有下列性质的 二叉树 ： 若它的左子树不空，则左子树上所有结点的值均小于它的 根结点 的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为 二叉排序树 。