leetcode_0104

题目

104. 二叉树的最大深度

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回它的最大深度 3 。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Tree:
'''
用来从数组中得到整个树的方法
'''
def getTreeFromList(self, L, index):
if index < len(L) and L[index] != None:
root = TreeNode(L[index])
root.right = self.getTreeFromList(L, (index+1)*2)
root.left = self.getTreeFromList(L, (index+1)*2-1)
return root
else:
return None


class Solution:
'''
主要的方法,其实很简单
'''
def maxDepth(self, root):
if not root:
return 0
else:
return 1 + max(self.maxDepth(root.right),self.maxDepth(root.left))

if __name__ == '__main__':
L = [3,9,20,None,None,15,7]
T = Tree()
root = T.getTreeFromList(L,0)
print(root)
a = Solution()
print(a.maxDepth(root))