04_二叉树的层次遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        value_list = []
        cur_node_list = [root]

        while len(cur_node_list):
            cur_val_list = []
            next_node_list = []
            for node in cur_node_list:
                if not node:
                    continue
                cur_val_list.append(node.val)
                next_node_list.extend([node.left, node.right])

            if cur_val_list:
                value_list.append(cur_val_list)
            cur_node_list = next_node_list
        return value_list


# leetcode 最优解 和我的思路一样 都是遍历当前层次的节点
class Solution2(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        cur = [root]
        out = [[root.val]]
        while(cur):
            new = []
            new_out = []
            for node in cur:
                if node.left:
                    new.append(node.left)
                    new_out.append(node.left.val)
                if node.right:
                    new.append(node.right)
                    new_out.append(node.right.val)
            cur = new
            if new_out:
                out.append(new_out)
        return out