Binary Tree Level Order Traversa

2016-11-27  本文已影响0人  无为无悔

For example: Given binary tree {3,9,20,#,#,15,7}, return
[
[3],
[9,20],
[15,7]
]



import java.util.*;

public class Solution {
    public List<List<Integer>> levelOrderTraverse(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null)
            return result;
        Queue<TreeNode> rootQueue = new LinkedList<>();
        Queue<TreeNode> leafQueue = new LinkedList<>();
        rootQueue.add(root);
        while(!rootQueue.isEmpty()) {
            List<Integer> levelRes = new ArrayList<>();
            while(!rootQueue.isEmpty()) {
                TreeNode p = rootQueue.poll();
                levelRes.add(p.val);
                if(p.left != null) leafQueue.add(p.left);
                if(p.right != null) leafQueue.add(p.right);
            }
            result.add(levelRes);
            // 交换上层和下层的队列
            Queue<TreeNode> tmp = rootQueue;
            rootQueue = leafQueue;
            leafQueue = tmp;
        }
        return result;
    }
}
上一篇 下一篇

猜你喜欢

热点阅读