#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
__project__ =  'leetcode'
__file__    =  '__init__.py'
__author__  =  'king'
__time__    =  '2020/2/10 16:53'


                              _ooOoo_
                             o8888888o
                             88" . "88
                             (| -_- |)
                             O\  =  /O
                          ____/`---'\____
                        .'  \\|     |//  `.
                       /  \\|||  :  |||//  \
                      /  _||||| -:- |||||-  \
                      |   | \\\  -  /// |   |
                      | \_|  ''\---/''  |   |
                      \  .-\__  `-`  ___/-. /
                    ___`. .'  /--.--\  `. . __
                 ."" '<  `.___\_<|>_/___.'  >'"".
                | | :  `- \`.;`\ _ /`;.`/ - ` : | |
                \  \ `-.   \_ __\ /__ _/   .-` /  /
           ======`-.____`-.___\_____/___.-`____.-'======
                              `=---='
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                       佛祖保佑        永无BUG
"""

"""

难度：中等

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树:[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：
[
  [3],
  [9,20],
  [15,7]
]
"""
from leetcode.lessons.binary_tree import TreeNode


class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        result = []

        level_nodes = [root]

        while level_nodes:
            new_level_nodes = []
            result.append([])

            for node in level_nodes:
                result[-1].append(node.val)
                if node.left:
                    new_level_nodes.append(node.left)
                if node.right:
                    new_level_nodes.append(node.right)

            level_nodes = new_level_nodes
        return result


root = TreeNode(3)
left = TreeNode(9)
right = TreeNode(20)
right.left = TreeNode(15)
right.right = TreeNode(7)
root.left = left
root.right = right

print(Solution().levelOrder(root))

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
__project__ =  'leetcode'
__file__    =  '__init__.py'
__author__  =  'king'
__time__    =  '2020/2/10 16:53'


                              _ooOoo_
                             o8888888o
                             88" . "88
                             (| -_- |)
                             O\  =  /O
                          ____/`---'\____
                        .'  \\|     |//  `.
                       /  \\|||  :  |||//  \
                      /  _||||| -:- |||||-  \
                      |   | \\\  -  /// |   |
                      | \_|  ''\---/''  |   |
                      \  .-\__  `-`  ___/-. /
                    ___`. .'  /--.--\  `. . __
                 ."" '<  `.___\_<|>_/___.'  >'"".
                | | :  `- \`.;`\ _ /`;.`/ - ` : | |
                \  \ `-.   \_ __\ /__ _/   .-` /  /
           ======`-.____`-.___\_____/___.-`____.-'======
                              `=---='
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                       佛祖保佑        永无BUG
"""

"""

难度：中等

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树:[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：
[
  [3],
  [9,20],
  [15,7]
]
"""
from leetcode.lessons.binary_tree import TreeNode


class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        result = []

        level_nodes = [root]

        while level_nodes:
            new_level_nodes = []
            result.append([])

            for node in level_nodes:
                result[-1].append(node.val)
                if node.left:
                    new_level_nodes.append(node.left)
                if node.right:
                    new_level_nodes.append(node.right)

            level_nodes = new_level_nodes
        return result


root = TreeNode(3)
left = TreeNode(9)
right = TreeNode(20)
right.left = TreeNode(15)
right.right = TreeNode(7)
root.left = left
root.right = right

print(Solution().levelOrder(root))

#!/usr/bin/env python # -*- coding: utf-8 -*- __project__ =  'leetcode' __file__    =  '__init__.py' __author__  =  'king' __time__    =  '2020/2/10 16:53'                                 _ooOoo_                              o8888888o                              88" . "88                              (| -_- |)                              O\  =  /O                           ____/`---'\____                         .'  \\|     |//  `.                        /  \\|||  :  |||//  \                       /  _||||| -:- |||||-  \                       |   | \\\  -  /// |   |                       | \_|  ''\---/''  |   |                       \  .-\__  `-`  ___/-. /                     ___`. .'  /--.--\  `. . __                  ."" '<  `.___\_<|>_/___.'  >'"".                 | | :  `- \`.;`\ _ /`;.`/ - ` : | |                 \  \ `-.   \_ __\ /__ _/   .-` /  /            ======`-.____`-.___\_____/___.-`____.-'======                               `=---='           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^                        佛祖保佑        永无BUG 难度：中等  给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。  例如: 给定二叉树:[3,9,20,null,null,15,7],      3    / \   9  20     /  \    15   7 返回其层次遍历结果： [   [3],   [9,20],   [15,7] ] :type root: TreeNode         :rtype: List[List[int]]