-
满二叉树
-
二叉搜索树
-
平衡二叉搜索树
-
二叉树存储 (链式，数组）
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
- 二叉树遍历 (递归，迭代），本质是深搜(dfs).
- 前序: 中左右 (pre-order)
- 中序: 左中右 (in-order)
- 后序: 左右中 (post-order)
144. 二叉树的前序遍历
- 思路
- example
- 递归
- 复杂度. 时间：O(n), 空间: O(n)
中左右
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def traversal(root):
if root == None:
return
res.append(root.val)
traversal(root.left)
traversal(root.right)
res = []
traversal(root)
return res
- 迭代
- 用list实现stack, 每次从stack pop一个node出来进行处理。
- 然后node.right先入栈，node.left后入栈 （进栈：先右后左；出栈：先左后右）。
- 空节点不入栈
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if root == None:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val) # node cannot be None
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
- 迭代“统一”写法, 真正自然写法。
-
利用stack和cur遍历 stack作为辅助
- 一条道走到黑。
- 走不动再从stack pop出来换方向（左-->右）。
-
利用stack和cur遍历 stack作为辅助
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
cur = root
stack = []
res = []
while cur or stack:
if cur:
res.append(cur.val)
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
cur = cur.right
return res
94. 二叉树的中序遍历
- 思路
- example
- 递归
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def traversal(root):
if root == None:
return
traversal(root.left)
res.append(root.val)
traversal(root.right)
res = []
traversal(root)
return res
- 迭代''统一''写法
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
cur = root
stack, res = [], []
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
145. 二叉树的后序遍历
- 思路
- example
- 递归
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def traversal(root):
if root == None:
return
traversal(root.left)
traversal(root.right)
res.append(root.val)
res = []
traversal(root)
return res
- 迭代
- 类似前序迭代遍历，利用对称性，反转结果list.
- 中右左 --> 左右中
- 类似前序迭代遍历，利用对称性，反转结果list.
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if root == None:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
res.reverse()
return res
- 迭代''统一''写法
中右左 反转成 左右中
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
cur = root
res, stack = [], []
while cur or stack:
if cur:
res.append(cur.val)
stack.append(cur)
cur = cur.right
else:
cur = stack.pop()
cur = cur.left
res.reverse() # !!!
return res
应用
- 快速排序: 二叉树的前序遍历
对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。
void sort(int[] nums, int lo, int hi) {
/****** 前序遍历位置 ******/
// 通过交换元素构建分界点 p
int p = partition(nums, lo, hi);
/************************/
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
- 归并排序: 二叉树的后序遍历
对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组就排好序了。
// 定义：排序 nums[lo..hi]
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
// 排序 nums[lo..mid]
sort(nums, lo, mid);
// 排序 nums[mid+1..hi]
sort(nums, mid + 1, hi);
/****** 后序位置 ******/
// 合并 nums[lo..mid] 和 nums[mid+1..hi]
merge(nums, lo, mid, hi);
/*********************/
}
- 二叉树题目的递归解法可以分两类思路
- 第一类是遍历一遍二叉树得出答案 (回溯）
- 第二类是通过分解问题计算出答案 （动规）
543. Diameter of Binary Tree
- 思路
- example
- 递归: 后序遍历 （自下而上）
递归返回值：以当前节点为root的子树的深度。
同时维护一个全局变量（或者递归参数）更新答案|直径。
每一条二叉树的「直径」长度，就是一个节点的左右子树的最大高度之和。遍历整棵树中的每个节点，然后通过每个节点的左右子树的最大深度算出每个节点的「直径」，最后把所有「直径」求个最大值即可。
遇到子树问题，首先想到的是给函数设置返回值，然后在后序位置做文章。
是否可以通过遍历一遍二叉树得到答案？如果不能的话，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案? 如果需要涉及到子树信息, 建议使用后续遍历.
本题：后序遍历的例题使用了「分解问题」的思路。因为当前节点接收并利用了子树返回的信息，这就意味着你把原问题分解成了当前节点 + 左右子树的子问题。
二叉树的「直径」长度，就是任意两个结点之间的路径长度。最长「直径」并不一定要穿过根结点：
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def traversal(root):
nonlocal res
if root == None:
return 0
left_diameter = traversal(root.left)
right_diameter = traversal(root.right)
cur_diameter = left_diameter + right_diameter
res = max(res, cur_diameter)
return max(left_diameter, right_diameter) + 1 # 以root为其中一个端点的最大diameter
res = 0
traversal(root)
return res
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def traversal(root):
nonlocal res
if root == None:
return 0
left = traversal(root.left)
right = traversal(root.right)
res = max(res, left+right)
return max(left, right)+1
res = 0
traversal(root)
return res
