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}
,3 / \ 9 20 / \ 15 7return its level order traversal as:
[ [3], [9,20], [15,7] ]A:
---------------简单的dfs, 每当看见一个节点,就加到结果上-----------------
public class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> all = new ArrayList<List<Integer>>(); int height = getHeight(root); for(int i =0;i<height;i++){ all.add(new ArrayList<Integer>()); } dfs(all,root,0); return all; } private void dfs(List<List<Integer>> all, TreeNode root, int level){ if(root == null) return; all.get(level).add(root.val); dfs(all,root.left,level+1); dfs(all,root.right,level+1); } private int getHeight(TreeNode root){ if(root == null) return 0; else return 1+Math.max(getHeight(root.left),getHeight(root.right)); } }
----------------------------第二遍,-------每次取下来一层, 放到一个Node 的list里, 同时保留Integer的一层---------------------
public class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> all = new LinkedList(); if(root == null) return all; List<TreeNode> lastLevel = new LinkedList(); List<Integer> l = new LinkedList(); lastLevel.add(root); l.add(root.val); all.add(l); while(lastLevel.isEmpty() ==false){ l = new LinkedList(); List<TreeNode> newLevel = new LinkedList(); for(TreeNode node:lastLevel){ if( node.left !=null ){ newLevel.add(node.left); l.add(node.left.val); } if( node.right !=null){ newLevel.add(node.right); l.add(node.right.val); } } lastLevel = newLevel; if(l.isEmpty()==false) all.add(l); } return all; } }
Mistakes:
1: 考虑到 stack的特性, 我们在加入的时候,要先push right child ,then left
2 艹~~~~~~~~~ BFS 是用Queue, 而不是stack, TNND
3: 每次要在while里重新new一个List, 单纯的clear()的话, ----由于其指针特性,会把all里的结果都clear掉
Learned:
1: 经常出现错误说“cannot create a generic array of .......”
Because of how generics in Java work, you cannot directly create an array of a generic type (such as
Map<String, Object>[] ). Instead, you create an array of the raw type (Map[] ) and cast it to Map<String, Object>[] . This will cause an unavoidable (but suppressible) compiler warning.This should work for what you need:
You may want to annotate the method this occurs in with @SupressWarnings("unchecked") , to prevent the warning from being shown. |
还有一个办法,就是 在new 的时候,不加generic type, 例如: 直接也不进行上面的cast
Stack<TreeNode>[] twoStack = new Stack[2];
3: Queue is an Interface not a class. , so,we cannot use them as class.
Instead, we need use LinkedList or PriorityQueue and etc to simulate it.
No comments:
Post a Comment