二叉树（python）

二叉树（python）"/>

二叉树（python）

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

二叉树的最大深度

遍历思维

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
class Solution:def maxDepth(self, root):res = 0depth = 0res = self.traverse(root, res, depth)return resdef traverse(self, root, res, depth):if not root:return resdepth += 1if 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 -= 1return res

分解思维

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

二叉树的直径

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

class Solution:def diameterOfTree(self, root):self.res = 0def maxDepth(root):if not root: return 0leftMax = maxDepth(root.left)rightMax = maxDepth(root.right)cur = leftMax + rightMaxself.res = max(cur, self.res)return 1 + max(leftMax, rightMax)maxDepth(root)return self.res

层序遍历

def levelTraverse(root):if not root: returnq = 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)