二叉树（python）

二叉树解体的思维模式分两类：
1、「遍历」的思维模式：是否可以通过遍历一遍二叉树得到答案？如果可以，用traverse函数配合外部变量实现。
2、「分解问题」的思维模式：是否可以通过子问题(子树)的答案推导出原文的答案？如果可以，写出递归函数的定义，并充分利用该函数的返回值。

二叉树的最大深度

遍历思维

class TreeNode:
	def __init__(self, val=0, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right
class Solution:
	def maxDepth(self, root):
		res = 0
		depth = 0
		res = self.traverse(root, res, depth)
		return res
	def traverse(self, root, res, depth):
		if not root:
			return res
		# 前序位置
		depth += 1
		if not root.left and not root.right:
			res = max(res, depth)
		res = self.traverse(root.left, res, depth)
		res = self.traverse(root.right, res, depth)
		# 后序位置
		depth -= 1
		return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

关于depth在前序位置+1后序位置-1的解释：
前序位置是进入一个节点的时候，后序位置是离开一个节点的时候，depth是记录当前递归到的节点深度，traverse可以理解为在二叉树上游走的一个指针，所以在离开该节点时，节点深度要减1的。

分解思维

class Solution:
	def mathDepth(self, root):
		if not root: return 0
		else:
			left_h = self.maxDepth(root.left)
			right_h = self.maxDepth(root.right)
			return max(left_h, right_h)+1
1
2
3
4
5
6
7

二叉树的直径

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度。这条路径可能经过也可能不经过根节点 root 。每一条二叉树的直径长度，就是一个节点的左右子树的最大深度之和.

class Solution:
	def diameterOfTree(self, root):
		self.res = 0
		def maxDepth(root):
			if not root: return 0
			leftMax = maxDepth(root.left)
			rightMax = maxDepth(root.right)
			cur = leftMax + rightMax
			self.res = max(cur, self.res)
			return 1 + max(leftMax, rightMax)
		maxDepth(root)
		return self.res
1
2
3
4
5
6
7
8
9
10
11
12

层序遍历

def levelTraverse(root):
	if not root: return
	q = deque()
	q.append(root)
	# while 循环和 for 循环分管从上到下和从左到右的遍历
	while q:
		level = len(q)
		for i in range(level):
			cur = q.popleft()
			if cur.left:
				q.append(cur.left)
			if cur.right:
				q.append(cur.right)
			
1
2
3
4
5
6
7
8
9
10
11
12
13
14