[leetcode]Binary Tree Level Order Traversal

新博文地址：

[leetcode]Binary Tree Level Order Traversal

Binary Tree Level Order Traversal

 

写道

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      7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.


OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:
     1
   /    \
 2      3
        /
      4
        \
         5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

二叉树的层次遍历BFS，与DFS一样，是很简单，基础的树的遍历方式。需要对每一层进行分别的解析，我很直接的维护了两个队列。不啰嗦

 

ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
    	    if(root == null){
    	    	return result;
    	    }
    	    ArrayDeque<TreeNode> pre = new ArrayDeque<TreeNode>();
    	    ArrayDeque<TreeNode> post = new ArrayDeque<TreeNode>();
    	    ArrayList<Integer> list = new ArrayList<Integer>();
    	    pre.offer(root);
    	    list.add(root.val);
    	    result.add(list);
    	    while(!pre.isEmpty()){
    	    	TreeNode tem = pre.poll();
    	    	if(tem.left != null){
    	    		post.offer(tem.left);
    	    	}
    	    	if(tem.right != null){
    	    		post.offer(tem.right);
    	    	}
    	    	if(pre.isEmpty()){//将post的值赋给pre，post清空，并将pre的val赋给list
    	    		if(post.isEmpty()){
    	    			break;
    	    		}
    	    		pre = post.clone();
    	    		post.clear();
    	    		ArrayList<Integer> temList = new ArrayList<Integer>();
    	    		for(TreeNode node: pre){
    	    			temList.add(node.val);
    	    		}
    	    		result.add(temList);
    	    	}
    	    }
    	    return result;
    }