二叉树的层次遍历

三道层次遍历题，同一个模板，这边用到的是两个队列

二叉树的层次遍历

LeetCode题目地址

def levelOrder(self, root):
        # write your code here
        result = []
        if root == None:
            return result
        q = [root]
        
        while len(q) != 0:
            new_q = []
            result.append([n.val for n in q])
            for node in q:
                if node.left:
                    new_q.append(node.left)
                if node.right:
                    new_q.append(node.right)    
            q = new_q
        return result

二叉树的层次遍历 加强版

LeetCode题目地址
给出一棵二叉树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）
q：上一层的所有点
new_q：根据q生成下一层的所有点

def levelOrderBottom(self, root):
        # write your code here
        self.results = []
        if not root:
            return self.results
        q = [root]
        while q:
            new_q = [] #存每一层的所有点
            self.results.append([n.val for n in q])
            for node in q:
                if node.left:
                    new_q.append(node.left)
                if node.right:
                    new_q.append(node.right)
            q = new_q
        return list(reversed(self.results))

二叉树的锯齿形层次遍历[ZigZag]

LeetCode地址

def zigzagLevelOrder(self, root):
        # write your code here
        result = []
        if root == None:
            return result
        q = [root]
        isReverse = False
        while len(q) != 0:
            new_q = []

            for node in q:
                if node.left:
                    new_q.append(node.left)
                if node.right:
                    new_q.append(node.right) 
            #把读取放在后面，防止reverse操作把q污染了       
            if isReverse:
                result.append([n.val for n in reversed(q)])
                isReverse = False
            else:
                result.append([n.val for n in q])
                isReverse = True
            q = new_q
        return result

最好的解决方法是只用一个队列

两个队列来帮助理解，在两个队列的基础上改进。
num_q：用len(q)代替

这是Java版本

python版本，针对本文第一题

def levelOrder(self, root):
        # write your code here
        result = []
        if root == None:
            return result
        q = [root]
        size = 0
        while len(q) != 0:
            size = len(q)#size一直在变化
            levelResult = []# levelResult存每一层的所有点
            for i in range(size):
                
                node = q.pop(0)
                levelResult.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)    
            result.append(levelResult)
        return result