美文网首页
leetcode102.Binary Tree Level Or

leetcode102.Binary Tree Level Or

作者: 就是果味熊 | 来源:发表于2020-07-02 23:02 被阅读0次

原题链接https://leetcode.com/problems/binary-tree-level-order-traversal/

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
常规层序遍历,用一个队列保存同级的结点,在遍历时将下一层结点入队,同时用count统计下一层结点数量,当本层遍历数量自增到上次保留的count值后,本层遍历结束,进入下一层结点,同时更新count值,得到的本层res,进入res_stack。直到队列为空,输出res_stack。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        deques = deque()
        res_stack = []
        deques.append(root)
        count = 1
        while deques:
            res = []
            n = count
            count = 0
            i = 0
            while i < n:
                item = deques.popleft()
                res.append(item.val)
                i += 1
                if item.left:
                    count += 1
                    deques.append(item.left)
                if item.right:
                    count += 1
                    deques.append(item.right)
            res_stack.append(res)
        return res_stack

相关文章

网友评论

      本文标题:leetcode102.Binary Tree Level Or

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