LeetCode 102.バイナリツリーレベルの順序トラバーサル-再帰的、反復的-Python、Javaソリューション

Leetcode 102 Binary Tree Level Order Traversal Recursive

---

LeetCodeタイトル列： LeetCodeソリューション
私が行ったすべてのLeetCodeトピックはこの列にあり、そのほとんどにJavaおよびPythonソリューションがあります。

---

二分木が与えられた場合、そのノードの値のレベル順走査を返します。 （つまり、左から右へ、レベルごとに）。

例えば：
与えられた二分木[3,9,20、null、null、15,7]、

3 / 9 20 / 15 7

レベル順トラバーサルを次のように返します。

[ [3], [9,20], [15,7] ]

---

この質問は、反復的または再帰的に行うことができます。
Python再帰ソリューション（比較的単純）：

class Solution: def levelOrder(self, root): ''' :type root: TreeNode :rtype: List[List[int]] ''' levels = [] if not root: return levels def helper(node, level): # start the current level if len(levels) == level: levels.append([]) # append the current node value levels[level].append(node.val) # process child nodes for the next level if node.left: helper(node.left, level + 1) if node.right: helper(node.right, level + 1) helper(root, 0) return levels

キューを使用したPython反復ソリューション

from collections import deque class Solution: def levelOrder(self, root): ''' :type root: TreeNode :rtype: List[List[int]] ''' levels = [] if not root: return levels level = 0 queue = deque([root,]) while queue: # start the current level levels.append([]) # number of elements in the current level level_length = len(queue) for i in range(level_length): node = queue.popleft() # fulfill the current level levels[level].append(node.val) # add child nodes of the current level # in the queue for the next level if node.left: queue.append(node.left) if node.right: queue.append(node.right) # go to next level level += 1 return levels

Java再帰ソリューション：

class Solution { List<List<Integer>> levels = new ArrayList<List<Integer>>() public void helper(TreeNode node, int level) { // start the current level if (levels.size() == level) levels.add(new ArrayList<Integer>()) // fulfil the current level levels.get(level).add(node.val) // process child nodes for the next level if (node.left != null) helper(node.left, level + 1) if (node.right != null) helper(node.right, level + 1) } public List<List<Integer>> levelOrder(TreeNode root) { if (root == null) return levels helper(root, 0) return levels } }

Java反復ソリューション：

class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> levels = new ArrayList<List<Integer>>() if (root == null) return levels Queue<TreeNode> queue = new LinkedList<TreeNode>() queue.add(root) int level = 0 while ( !queue.isEmpty() ) { // start the current level levels.add(new ArrayList<Integer>()) // number of elements in the current level int level_length = queue.size() for(int i = 0 i < level_length ++i) { TreeNode node = queue.remove() // fulfill the current level levels.get(level).add(node.val) // add child nodes of the current level // in the queue for the next level if (node.left != null) queue.add(node.left) if (node.right != null) queue.add(node.right) } // go to next level level++ } return levels } }