首页 > 其他 > 详细

[Lintcode] Binary Tree Level Order Traversal

时间:2015-10-07 13:24:07      阅读:238      评论:0      收藏:0      [点我收藏+]

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).

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]
]

 

SOLUTION :

这个题有很多解法,包括用两个queue,一个queue+dummy node 以及只用一个queue的,这里就只说最优解,1 queue的了。

本题借鉴了大神的总结:http://www.1point3acres.com/bbs/thread-139294-1-1.html

基本上几个level order 的二叉树遍历都可以用这套思路。

思路:用queue去模拟层序遍历的过程,就是说要向queue中一层一层的输入,再输出,但是怎么保证输入的是同一层呢,我们用到一个变量,queue.size(),这个很关键,它保证了内层循环(负责向queue输入节点以及从queue拿出节点加入list中)执行次数就是这一层节点的个数。在实现时候的具体思想就是,拿出一个点,就把这个点的左右儿子加入到queue中,从任一一层二叉树来看,就是当这一层的所有点抖拿出来了之后,同时这些点的所有左右儿子也都加进去了。具体实现看代码:

注意事项,queue用LinkedList模拟,queue输入输出分别是add(),remove()。

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Level order a list of lists of integer
     */
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (root == null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++){
                TreeNode cur = queue.remove();
                if (cur.left != null){
                    queue.add(cur.left);
                }
                if (cur.right != null){
                    queue.add(cur.right);
                }
                list.add(cur.val);
            }
            result.add(new ArrayList<Integer>(list));
        }
        return result;
    }
}

  

[Lintcode] Binary Tree Level Order Traversal

原文:http://www.cnblogs.com/tritritri/p/4858504.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!