美文网首页
2019-08-23 剑指 把二叉树打印成多行

2019-08-23 剑指 把二叉树打印成多行

作者: mztkenan | 来源:发表于2019-08-23 09:19 被阅读0次

    10min,逻辑很简单,使用两个栈,就不用考虑下一层有多少个节点了

    class Solution:
        # 返回二维列表[[1,2],[4,5]]
        def Print(self, pRoot:TreeNode):
            if not pRoot:return []
            q1,q2=deque(),deque()
            res=[]
            q1.append(pRoot)
            while q1:
                tmp=[]
                while q1:
                    front = q1.popleft()
                    tmp.append(front.val)
                    if front.left:q2.append(front.left)
                    if front.right:q2.append(front.right)
                res.append(tmp)
                q1=q2
                q2=deque()
            return res
    

    7min,是前序遍历,但是通过函数参数把层数记录下来,载入到相对应的list中,特别清晰易懂,很妙

    class Solution2:
        # 返回二维列表[[1,2],[4,5]]
        def Print(self, pRoot):
            res=[]
            self.dfs(pRoot,1,res)
            return res
    
        def dfs(self,pRoot:TreeNode,depth,res:List):
            if not pRoot:return
            if depth>len(res):res.append([pRoot.val]) # 笔误写成res
            else:res[depth-1].append(pRoot.val)
            self.dfs(pRoot.left,depth+1,res)
            self.dfs(pRoot.right,depth+1,res)  # 函数参数没写全
    

    相关文章

      网友评论

          本文标题:2019-08-23 剑指 把二叉树打印成多行

          本文链接:https://www.haomeiwen.com/subject/wizasctx.html