PYTHON Three_way_to_solve_this_question
二叉树的最大深度
http://www.nowcoder.com/questionTerminal/8a2b2bf6c19b4f23a9bdb9b233eefa73
First:
Change the value of the tree to the depth of the tree
class Solution: def maxDepth(self , root ): if root == None:return 0 depth = 1 q = list() root.val = 1 q.append(root) while(q!=[]): node = q.pop() if node.val>depth:depth = node.val if node.left!=None:node.left.val = node.val+1;q.append(node.left) if node.right!=None:node.right.val = node.val+1;q.append(node.right) return depth
Second
Traversing one layer depth+=1
class Solution: def maxDepth(self , root ): if root == None :return 0 depth = 0 cur = list() cur.append(root) while(cur!=[]): depth+=1 tmp = list() for i in cur: if i.left!=None:tmp.append(i.left) if i.right!=None:tmp.append(i.right) cur = [i for i in tmp if i] return depth
third
Postorder traversal
class Solution: def maxDepth(self , root ): # write code here if root is None: return 0 return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))