前言
新的一年，好好学习。尝试用python写写代码。
正文
问题来源
本问题来自leetcode上的104题。
问题描述
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
分析：
有些愚蠢的我
第一反应就是用回溯法解这个题
# 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 __init__(self):
self.dep = 0
self.max = 0
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.backtrack(root)
return self.max
def backtrack(self, root):
if not root :
return
self.dep += 1
if self.max < self.dep :
self.max = self.dep
self.maxDepth(root.left)
self.maxDepth(root.right)
self.dep -= 1
其实可以用简单递归就可以解决
递归版（别人）
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
depth = max(self.maxDepth(root.left),self.maxDepth(root.right))+1
return depth
非递归版本（别人）
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: return 0
if not root.left and not root.right: return 1
stack = [root]
depth = 0
while stack:
new_stack = []
for node in stack:
if node.left:
new_stack.append(node.left)
if node.right:
new_stack.append(node.right)
depth += 1
stack = new_stack
return depth
总结：
勤思考。
结语
不管怎么样好好加油。
