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

对于一棵树进行level序遍历。水平遍历即遍历结束当前行以后再遍历下一行，并将每行的结果按行填入到数组中返回。

递归

这道题还是很基础的啦。利用水平遍历的话，我们只需要知道当前元素在树中的高度就可以知道应当插入到那个数组中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    levelOrder(root, 0, result);
    return result;
}

public void levelOrder(TreeNode treeNode, int height, List<List<Integer>> result){
    if(treeNode == null) return;
    if(height>result.size()-1){
        result.add(new ArrayList<Integer>());
    }
    result.get(height).add(treeNode.val);
    levelOrder(treeNode.left, height+1, result);
    levelOrder(treeNode.right, height+1, result);
}

使用队列

其实在数据结构的教材中为了说明栈和队列的使用，分别举的就是中序遍历和水平遍历的例子。在这里我们同样可以使用队列的先进先出的机制将同一行的元素读入后，再逐个读出，并在同时插入下一行中的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<List<Integer>> levelOrder2(TreeNode root){
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(root==null)return result;
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int levNum = queue.size();
        List<Integer> temp = new ArrayList<Integer>();
        for(int i = 0 ; i<levNum ; i++){
            if(queue.peek().left!=null)queue.offer(queue.peek().left);
            if(queue.peek().right!=null)queue.offer(queue.peek().right);
            temp.add(queue.poll().val);
        }
        result.add(temp);
    }
    return result;
}