LeetCodeブラシ問題(三)

102. Binary Tree Level Order Traversal
Description
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
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]
]

構想とコード
ここでの問題の要件は,階層が二叉木を遍歴し,各層が1行であり,2次元配列を出力することである.ツリーの階層遍歴メソッドを使用して、各レイヤの要素の値を格納するためのリストを設定し、再帰的なメソッドで、遍歴していないサブツリーをリストに格納します.リストが空でない場合は、次のレイヤノードがあることを示します.遍歴を続行し、そのレイヤの要素の値をresリストに格納し、resリストを出力リストに追加します.対応するPythonコードは以下の通りです.

# 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]]
        """
        if not root:
            return []
        outList=[]
        queue = [root]
        while queue:
            nextQueue = []
            res = []
            for point in queue:
                res.append(point.val)
                if point.left:
                    nextQueue.append(point.left)
                if point.right:
                    nextQueue.append(point.right)
                
            queue = nextQueue
            outList.append(res)
        return outList

実行時間24 ms、メモリ消費量12.1 MB.もちろん上のツリーの情報を格納するためのリストはキューで格納することもできますが、Pythonのキューもリストで実現されており、リストよりも効果的ではありません.キューのコードは以下の通りです.

# 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]]
        """
        if not root:
            return []
        outList=[]
        queue = [root]
        while queue:
            res = []
            i = 0
            nextQueue = []
            while i < len(queue):
                point = queue.pop(0)
                res.append(point.val)
                if point.left:
                    nextQueue.append(point.left)
                if point.right:
                    nextQueue.append(point.right)
            i += 1
            outList.append(res)
            queue = nextQueue
        return outList

ノード情報をキューで格納するため、ループの位置を1つのタグiで記録する必要があります.上のコードの実行時間は36 msで、メモリの12.3 MBを占有します.
94. Binary Tree Inorder Traversal
Description
Given a binary tree, return the inorder traversal of its nodes’ values.
Example 1

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Follow up
Recursive solution is trivial, could you do it iteratively?
構想とコード
上記の例によれば,問題は我々の中序が二叉木を遍歴し,中序遍歴後の要素リストを返すことを要求していることがわかる.ここではまず再帰的な方法で二叉木を巡り,対応するPythonコードは以下の通りである.

# 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 inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        #       
        resList = [] 
        if root:
            resList += self.inorderTraversal(root.left)
            resList.append(root.val)
            resList += self.inorderTraversal(root.right)
        return resList