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))
全部评论

相关推荐

点赞 评论 收藏
分享
03-29 14:19
门头沟学院 Java
你背过凌晨4点的八股文么:加油同学,人生的容错率很高,只是一个暑期罢了,后面还有很多机会!
点赞 评论 收藏
分享
评论
2
1
分享

创作者周榜

更多
牛客网
牛客企业服务