流利说编程题
题目：输出二叉搜索树的层序遍历
输入：
第一行：N（二叉搜索书的节点数）
第二行：N个节点的值，空格隔开，换行结束
输出：
二叉搜索树的层序遍历结果
例子：
输入：
9
8 3 1 6 4 7 10 14 13
输出：
8 3 10 1 6 14 4 7 13
直接贴代码（虽然没在考试时间完成😥，但还是写了一份完整代码，仅供参考）
import java.util.*;
public class TopDownLeftRight {
public static class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
if (root == null) {
return null;
}
ArrayList<Integer> result = new ArrayList<>();
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.peek();
result.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
queue.poll();
}
return result;
}
public TreeNode GenerateTree(int[] arr, int start, int end) {
if (start == end) {
return new TreeNode(arr[start]);
}
if (start > end) {
return null;
}
TreeNode root = new TreeNode(arr[start]);
int i = start + 1;
for (; i < end; i++) {
if (arr[i] > arr[start]) {
break;
}
}
if (i == arr.length - 1) {
root.left = GenerateTree(arr, start + 1, i);
} else {
root.left = GenerateTree(arr, start + 1, i - 1);
}
if (i <= end && arr[i] > arr[start]) {
root.right = GenerateTree(arr, i, end);
}
return root;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int NodeNum = sc.nextInt();
int[] NodeArr = new int[NodeNum];
for (int i = 0; i < NodeNum; i++) {
NodeArr[i] = sc.nextInt();
}
TopDownLeftRight topDownLeftRight = new TopDownLeftRight();
TreeNode root = topDownLeftRight.GenerateTree(NodeArr, 0, NodeNum - 1);
ArrayList<Integer> re = topDownLeftRight.PrintFromTopToBottom(root);
for (int i = 0; i < re.size(); i++) {
System.out.print(re.get(i));
System.out.print(" ");
}
}
}
