題目描述

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

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

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

** 示例:** 給定二叉樹 [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,與預期一致。代碼提交運行結果如下,還有很大的提升空間!

推薦閱讀:

相關文章