题解 | #牛群分层排列#

知识点

树，层序遍历

解题思路

按照层序遍历，一层一层遍历，保存每一层节点值到字符串中，将字符串保存list，转成数组返回。

层序遍历我们可以使用两个队列，一个外层队列，一个内层队列；外层队列有值全部转移到内层队列，内层队列节点取出，如果有左右子树又放到外层队列。

Java题解

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return string字符串一维数组
     */
    public String[] levelOrder (TreeNode root) {
        // write code here
        Deque<TreeNode> outer = new LinkedList<>();
        Deque<TreeNode> inner = new LinkedList<>();
        if(root != null) outer.offerFirst(root);
        List<String> list = new ArrayList<>();
        while (!outer.isEmpty()){

            while(!outer.isEmpty()){
                inner.offerFirst(outer.pollLast());
            }
            StringBuilder sb = new StringBuilder();
            while(!inner.isEmpty()){
                TreeNode treeNode = inner.pollLast();
                sb.append(treeNode.val);
                if(treeNode.left != null) outer.offerFirst(treeNode.left);
                if(treeNode.right != null) outer.offerFirst(treeNode.right);
            }
            list.add(sb.toString());
        }
        return list.toArray(new String[0]);
    }
}