三个月算法进阶--day26
目录
二叉树
递归与迭代 深度优先遍历与广度优先遍历
二叉树深度
不遍历每个节点怎么知道深度？
时间复杂度O(n)
二叉树天然是可以分解为小规模问题的问题，递归具有回溯特性
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
class Solution:
def maxDepth(self, root: TreeNode) -> int:
return 0 if not root else max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
广度优先，根据上层导出下层，写法上是迭代，思想上是动规
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
tmp = [root]
ans = 0
while tmp:
ans += 1
tmp = [i.left for i in tmp if i.left] + [i.right for i in tmp if i.right]
return ans
根节点是否存在
BFS与DFS
栈与队列