題目描述

給定一個二叉樹，找出其最大深度。

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

說明: 葉子節點是指沒有子節點的節點。

** 示例：** 給定二叉樹 [3,9,20,null,null,15,7]，

3
/
9 20
/
15 7

返回它的最大深度 3 。

解決思路

採用廣度優先搜索(BFS)從根節點開始，逐層遍歷，每遍歷完一層深度加1。

代碼

class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class Solution(object):
def maxDepth(self, root):
if not root:
return 0
nodes = [root]
s = 0
while len(nodes)>0:
s += 1
tmp = []
for node in nodes:
if hasattr(node, "left") and node.left is not None:
tmp.append(node.left)
if hasattr(node, "right") and node.right is not None:
tmp.append(node.right)
nodes = tmp
print(len(nodes))
return s

首先，創建nodes變數存放每一層的node，預先將root節點放入，只要nodes不為空就代表還有節點沒有被遍歷到，s代表樹的深度，tmp是一個臨時列表。因為nodes存放每一層的所有節點，因此可以通過循環將每一個節點的子節點依次放入一個tmp列表中，待nodes循環結束，將tmp賦值給nodes變數，進行下一輪的判斷，當nodes為空時程序退出，返回s。

測試

首先生成一顆樹。

p = TreeNode(1)
p.left = TreeNode(2)
p.right = TreeNode(3)
p.left.left = TreeNode(4)
p.right.left = TreeNode(5)
p.right.right = TreeNode(6)
p.left.left.left = TreeNode(7)
p.right.right.left = TreeNode(8)
p.right.right.left.right = TreeNode(9)


樹的結構如下，共有5層，共計9個節點。

solution = Solution()
depth = solution.maxDepth(p)
print(depth)


最終的結果為5，與預期一致。代碼提交運行結果如下，還有很大的提升空間！

推薦閱讀：