给定一个二叉树,找出其最大深度。(老规矩前两个我写的,后面我抄的,尤其是最后一个递归真是经典)
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def maxDepth(self, root):
"""
这个是根据maxDepth1,将maxDepth2改进的
:type root: TreeNo de
:rtype: int
"""
if not root:
return 0
queue = [root]
count = 0
while queue:
count += 1
size = len(queue)
for i in range(size):
node_ = queue.pop(0)
if node_ and node_.left:
queue.append(node_.left)
if node_ and node_.right:
queue.append(node_.right)
return count
def maxDepth2(self, root):
"""
如果直接给出数组的长度,可以通过满二叉树的节点公式2**n -1(n表示层数,公式整体算出来的所有节点数)
但是这个没有所以都要经过遍历直接使用队列,类似于
:type root: TreeNo de
:rtype: int
"""
if not root:
return 0
queue = [root]
ret_list = []
while queue:
size = len(queue)
inner_list = []
for i in range(size):
node_ = queue.pop(0)
inner_list.append(node_)
if node_ and node_.left:
queue.append(node_.left)
if node_ and node_.right:
queue.append(node_.right)
ret_list.append(inner_list)
return len(ret_list)
def maxDepth1(self, root):
"""
这个挺好直接深度遍历使用一个变量统计层数就可以了,看来我的代码还可以改改
:type root: TreeNode
:rtype: int
"""
# bfs
if not root:
return 0
else:
queue = [(1, root)]
while queue:
depth, node = queue.pop(0)
if node.left:
queue.append((depth + 1, node.left))
if node.right:
queue.append((depth + 1, node.right))
return depth
def maxDepth3(self, root):
"""
内存消耗最少,经典递归*****
:type root: TreeNode
:rtype: int
"""
if root == None:
return 0
else:
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
if __name__ == '__main__':
s1 = Solution()
head = [4, 5, 1, 9]; node = 1
s1.maxDepth(head, node)