剑指offer-二叉树

目录

• 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
• 把二叉树打印成多行
  • 层次遍历 迭代 py2

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