当前位置:首页 » JAVA技术教程

leetcode-102.+Binary+Tree+Level+Order+Traversal

2016-12-27 09:46 本站整理 浏览(4)

leetcode-102. 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,null,null,15,7],

3

/ \

9 20

/ \

15 7

return its level order traversal as:

[

[3],

[9,20],

[15,7]

]

层次遍历,用FIFO比较合适。

新建一个FIFO队列引用,为每一层维护一个FIFO队列然后遍历这个队列,同时添加当前元素和将当前元素的左右子节点分别添加到下一层FIFO队列中。

[code]/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        List<TreeNode> tmp = new ArrayList<TreeNode>();
        if(root!=null) tmp.add(root);
        while(tmp.size()!=0){
            List<Integer> ad = new ArrayList<Integer>();
            ArrayList<TreeNode> replace = new ArrayList<TreeNode>();
            for(TreeNode node : tmp){
                if(node.left!=null)
                    replace.add(node.left);
                if(node.right!=null)
                    replace.add(node.right);
                ad.add(node.val);
            }
            tmp = replace;
            ret.add(ad);
        }
        return ret;
    }
}