描述
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
return its level order traversal as:
1 2 3 4 5
| [ [3], [9,20], [15,7] ]
|
分析
层次遍历,而且顺序正常,按常规思路写即可,可以用递归,也可以用迭代,有意思的是代码与(E) Binary Tree Level Order Traversal II几乎一样,只有最后一行不同。用迭代的方式,时间复杂度是O(n),空间复杂度是O(n)。
解决方案1(Python)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
class Solution(object): def levelOrder(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if not root: return [] result = [] next_level = [root] while next_level: now_level = next_level result.append(map(lambda x: x.val, now_level)) next_level = [] for item in now_level: if item.left: next_level.append(item.left) if item.right: next_level.append(item.right) return result
|
解决方案2(C++)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
|
class Solution { public: vector<vector<int>> result; void leveltravel(TreeNode* root, int level) { if(root == NULL) { return; } if(level == result.size()) { vector<int> v; result.push_back(v); } result[level].push_back(root->val); leveltravel(root->left, level+1); leveltravel(root->right, level+1); } vector<vector<int>> levelOrder(TreeNode* root) { leveltravel(root, 0); return vector<vector<int>>(result.begin(), result.end()); } };
|
解决方案3(Java)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new LinkedList<List<Integer>>(); DFS(root, 0, result); return result; } private void DFS(TreeNode node, int i, List<List<Integer>> result) { if (node == null) { return; } if (i == result.size()) { result.add(result.size(), new LinkedList<Integer>()); } result.get(i).add(node.val); DFS(node.left, i+1, result); DFS(node.right, i+1, result); } }
|
解决方案4(golang)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
|
func levelOrder(root *TreeNode) [][]int { result := [][]int{} if root == nil { return result } queue := []*TreeNode{root} for i := 0; len(queue) > 0; i++ { result = append(result, []int{}) nowQueue := []*TreeNode{} for j := 0; j < len(queue); j++ { node := queue[j] result[i] = append(result[i], node.Val) if node.Left != nil { nowQueue = append(nowQueue, node.Left) } if node.Right != nil { nowQueue = append(nowQueue, node.Right) } } queue = nowQueue } return result }
|
相关问题