二叉树(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)
更多推荐
二叉树(python)
发布评论