102.Binary-Tree-Level-Order-Traversal.md

102. Binary Tree Level Order Traversal

---

题目地址

http://www.lintcode.com/problem/binary-tree-level-order-traversal/

http://www.jiuzhang.com/solutions/binary-tree-level-order-traversal/

https://leetcode.com/problems/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]
]

代码

Approach 1: BFS

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
     List<List<Integer>> result = new ArrayList<List<Integer>>();

    if (root == null) return result;

    Queue<TreeNode> queque = new LinkedList<TreeNode>();
    queue.offer(root);

    while (!queue.isEmpty()) {
      ArrayList<Integer> level = new ArrayList<Integer>();
      int size = queue.size();
      for (int i = 0; i < size; i++) {
        TreeNode head = queue.poll();
        level.add(head.val);
        if (head.left != null) {
          queue.offer(head.left);
        }
        if (head.right != null) {
          queue.offer(head.right);
        }
      }
      result.add(level);
    }

    return result;
  }
}

Approach 2: DFS

class Solution {
  public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> results = new ArrayList<List<Integer>>();
    if (root == null)    return results;

    int maxLevel = 0;
    while (true) {
      List<Integer> level = new ArrayList<Integer>();
      dfs(root, level, 0, maxLevel);
      if (level.size() == 0) {
        break;
      }

      results.add(level);
      maxLevel++;
    }

    return results;
  }

  private void dfs(TreeNode root, List<Integer> level, int curtLevel, int maxLevel) {
    if (root == null || curtLevel > maxLevel) return;

    if (curtLevel == maxLevel) {
      level.add(root.val);
      return;
    }

    dfs(root.left, level, curtLevel + 1, maxLevel);
    dfs(root.right, level, curtLevel + 1, maxLevel);
  }
}

Approach 3; BFS, two queues

class Solution {
  public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if (root == null) return result;

    List<TreeNode> Q1 = new ArrayList<TreeNode>();
    List<TreeNode> Q2 = new ArrayList<TreeNode>();

    Q1.add(root);
    while (Q1.size() != 0) {
      List<Integer> level = new ArrayList<Integer>();
      Q2.clear();
      for (int i = 0; i < Q1.size(); i++) {
        TreeNode node = Q1.get(i);
        level.add(node.val);
        if (node.left != null) {
          Q2.add(node.left);
        }
        if (node.right != null) {
          Q2.add(node.right);
        }
      }

      List<TreeNode> temp = Q1;
      Q1 = Q2;
      Q2 = temp;

      result.add(level);
    }

    return result;
  }
}