Question: https://oj.leetcode.com/problems/binary-tree-level-order-traversal/
Question Name: Binary Tree Level Order Traversal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | # Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param root, a tree node # @return a list of lists of integers def levelOrder(self, root): if root == None: return [] # In the first stage, we store hte nodes (not their value). result = [] nextLayer = [root] while len(nextLayer) != 0: result.append(nextLayer) # Gather the nodes in the next deeper layer. nextLayer = [] for father in result[-1]: if father.left != None: nextLayer.append(father.left) if father.right != None: nextLayer.append(father.right) # In the second stage, we convert the nodes into their values. result = [[node.val for node in layer] for layer in result] return result |
Hi – Well , I m a bit confused with this one particular line of code :
“for father in result[-1]: ”
This looks up only the last element in the result ( and adds its children to the Queue (ie) NextLayer .
What if you have two elements – aren’t you missing the internal element (since you are just looking at the top most element ? )
BTW – just wanted to clarify ; I m pretty sure the OJ accepted this solution and its correct. Just wanted to clarify for my understanding.
Sorry for the bad style. Python is dynamic type. Actually the type of result inside while loop is different from the type after while loop.
Inside while loop, the result is a list of list of nodes like: [[first node in first layer, second node in second layer], [first node in second layer, … …], [], …]
After the while loop, we change the type of result:
result = [[node.val for node in layer] for layer in result]
Then it is a list of nodes, such as [first node in first layer, second node in second layer, first node in second layer, …]