python——DFS+BFS

简介

本篇笔记主要记录,运用DFS或BFS算法求解二叉树最大深度问题。

二叉树最大深度

题目来源:LeeCode104: Maximum Depth of Binary Tree

解法一

DFS(递归)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
return 1+max(self.maxDepth(root.left),self.maxDepth(root.right)) if root else 0

解法二

BFS、队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
queue,h=[root],0
while queue:
h+=1
for i in range(0,len(queue)):
node=queue.pop(0)
queue.extend(filter(None,[node.left,node.right]))
return h

分享