T55-二叉樹的深度(https://www.nowcoder.com/practice/435fb86331474282a3499955f0a41e8b?tpId=13&tqId=11191&tPage=2&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking)

迭代和遞歸 py2

python的層次遍歷
迭代 與"從上往下打印二叉樹"那一題不同的是，那個只需要一個隊列
這個由于要保存層數，所以需要用到next_queue這個輔助對列

#迭代
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if not pRoot:
            return 0
        queue = [pRoot]
        next_queue = []
        i = 0
        while queue&nbs***bsp;next_queue:
            i+=1
            while queue:
                node = queue.pop(0)
                if node.left:
                    next_queue.append(node.left)
                if node.right:
                    next_queue.append(node.right)
            queue = next_queue
            next_queue = []
        return i

#遞歸
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if not pRoot:
            return 0
        left = self.TreeDepth(pRoot.left)
        right = self.TreeDepth(pRoot.right)
        return left+1 if left>right else right+1

把二叉樹打印成多行

層次遍歷 迭代 py2

這個就是二叉樹層次遍歷需要返回二維數組的情況啦

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二維列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res = []
        queue,next_queue = [pRoot],[]
        while queue or next_queue:
            res.append([])
            while queue:
                node = queue.pop(0)
                res[-1].append(node.val)
                if node.left:
                    next_queue.append(node.left)
                if node.right:
                    next_queue.append(node.right)    
            queue = next_queue
            next_queue = []
        return res