问题描述:
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
方法1:
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root == None:
return 0
def depth(self,root,ans):
if root == None:
return ans
else:
ans += 1
ldepth = depth(self,root.left,ans)
rdepth = depth(self,root.right,ans)
if ldepth > rdepth :
return ldepth
else:
return rdepth
return depth(self,root,0)
简体:
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
简体2:
class Solution(object):
@classmethod
def maxDepth(self, root):
if root == None:
return 0 left = Solution.maxDepth(root.left) +1
right = Solution.maxDepth(root.right) +1 return max(left, right)
递归取左右子树高度的较大者
2018-09-07 20:21:23