How do you print out the nodes of a tree in level-order (i.e. first level, then 2nd level, then 3rd level, etc.)

[GingerBear]

source: https://sites.google.com/site/steveyegge2/five-essential-phone-screen-questions

[dianadujing]

Can you explain the problem in an easier way?

[GingerBear]

@dianadujing 返回一个二维数组，每个元素里是树的这一层的所有node。

主要是熟悉一下Tree的数据结构，以及能快速写出广度优先搜索。

[GingerBear]

原来不是用广度优先搜索，用普通的递归方法遍历树都可以，只要在递归的时候把level记住，当做索引存到数组里。

static void levelTree(TreeNode root) {
    ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
    int level = 0;
    levelTreeHelper(root, ret, level);
    int i = 0;
    for(ArrayList<Integer> layer: ret) {
        System.out.println("level "+ i + ": ");
        for(int v: layer) {
            System.out.print(v + " ");
        }
        System.out.println("");
        i++;
    }
}

static void levelTreeHelper(TreeNode root, ArrayList<ArrayList<Integer>> ret, int level) {
    if (root == null) return;
    if (level >= ret.size()) {
        ret.add(level, new ArrayList<Integer>());
    }
    ret.get(level).add(root.value);
    levelTreeHelper(root.left, ret, level+1);
    levelTreeHelper(root.right, ret, level+1);
}

顺便附上二叉树的广度优先搜索，用动态的Queue实现。

static void printTree(TreeNode root) {
    Queue<TreeNode> q = new Queue<TreeNode>();
    q.enqueue(root);
    while (!q.isEmpty()) {
        TreeNode n = q.dequeue();
        if (n == null) continue;
        System.out.println(n.value);
        q.enqueue(n.left);
        q.enqueue(n.right);
    }
}

讨论

这几个二叉树遍历的时间复杂度和空间复杂度待分析。

[dianadujing]

Where is the question for today?

[GingerBear]

@dianadujing 今天你来出一题吧

[dianadujing]

@GingerBear 我不会出题，做题都做不出来呢。。。

[GingerBear]

@dianadujing 那我就出一道经典的找第K大的元素的题吧

[yuweizhan]

import java.util.*;

/**
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode(int x) {val = x;}
 * }
 */
public class LevelOrderTraverse {
  static void levelOrderTraverse(TreeNode root) {
    // null check
    if (root == null)
      return;

    // BFS with queue
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    // node count 
    int currentLevelCount = 1;
    int nextLevelCount = 0;

    while (!queue.isEmpty()) {
      while (currentLevelCount > 0) {
        TreeNode n = queue.poll();
        // add child nodes to the queue
        if (n.left != null) {
          queue.add(n.left);
          nextLevelCount++;
        }
        if (n.right != null) {
          queue.add(n.right);
          nextLevelCount++;
        }
        System.out.print(n.val + " ");
        currentLevelCount--;
      }

      // go to next level
      currentLevelCount = nextLevelCount;
      nextLevelCount = 0;
      System.out.print("\n");
    }
  }

  // test
  public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    root.right.left = new TreeNode(6);
    root.right.right = new TreeNode(7);
    levelOrderTraverse(root);
  }
}

Result: 1 2 3 4 5 6 7