Leetcode204 二叉树的最大深度
【题目描述】
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
【解题思路】
对二叉树进行层序遍历,记录遍历过的层数。具体操作为,使用队列,根节点入队,随后记录队列长度,并进入for循环。这样可保证每次只遍历一层,在遍历时,将每个节点弹出队列,随后将弹出节点的非空子节点入队。每一次for循环结束,代表遍历一层。当队列长度为0时,结束遍历。
【代码】
# 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 root==None:
return 0
else:
queue=[root]
level=0
while len(queue)!=0:
size=len(queue)
for i in range(size):
tmp=queue[0]
queue.pop(0)
if tmp.left!=None:
queue.append(tmp.left)
if tmp.right!=None:
queue.append(tmp.right)
level=level+1
return level
【结果】
【反思】
目前执行速度最快的程序如下:
# 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
return 1 + max(self.maxDepth(root.left),self.maxDepth(root.right))
采用递归的思路,去递归遍历节点的左右子树,每进一层,递归加1。