“抱佛脚”系列（代码部分）； 所有代码均基于 Python3；
记号LC{xx}表示 Leetcode 第 xx 题，例如LC20表示 Leetcode 第 20题。
“树”的定义
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
基础：树的遍历
中序遍历（LC94）：
# 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
前序遍历（LC144）：
# 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
层序遍历 （LC02）(广度优先，BFS)：
- 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if root is None:
return []
res = []
nodes_next = [root]
while len(nodes_next):
res.append([nd.val for nd in nodes_next])
tmp = []
for node in nodes_next:
if node.left: tmp.append(node.left)
if node.right: tmp.append(node.right)
nodes_next = tmp
return res
高频题目
LC108 - 将有序数组转化为二叉搜索树
链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
- 二分，找到数组终点
- 递归构建
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if len(nums) <= 0:
return
elif len(nums) <= 1:
return TreeNode(val = nums[0])
mid = len(nums) // 2
root = TreeNode(
val = nums[mid],
left = self.sortedArrayToBST(nums[: mid]),
right = self.sortedArrayToBST(nums[mid + 1: ])
)
return root
LC105 - 从前序遍历和中序遍历构造二叉树
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if not len(preorder): return None
root_val = preorder[0]
root_loc = inorder.index(root_val) # 左数第一个匹配元素的下标
return TreeNode(
root_val,
left = self.buildTree(preorder[1: root_loc + 1], inorder[: root_loc]),
right = self.buildTree(preorder[root_loc + 1: ], inorder[root_loc + 1: ])
)