Daily LeetCode – day0024 0655. Print Binary Tree

// 0655. Print Binary Tree
class Solution {
    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> values = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean hasNextLevel = true;
        int bigBlank = 0;
        while (hasNextLevel) {
            bigBlank = bigBlank * 2 + 1;
            hasNextLevel = false;
            int queueSize = queue.size();
            List<String> rowOfValues = new ArrayList<>();
            for (int i = 0; i < queueSize; ++i) {
                TreeNode front = queue.poll();
                if (front == null) {
                    rowOfValues.add("");
                    queue.offer(null);
                    queue.offer(null);
                } else {
                    rowOfValues.add(String.valueOf(front.val));
                    queue.offer(front.left);
                    queue.offer(front.right);
                    if (front.left != null || front.right != null) hasNextLevel = true;
                }
            }
            values.add(rowOfValues);
        }
        int smallBlank = (bigBlank - 1) / 2;
        List<List<String>> ans = new ArrayList<>();
        for (int i = 0; i < values.size(); ++i) {
            List<String> rowOfValues = values.get(i);
            List<String> rowOfAns = new ArrayList<>();
            for (int j = 0; j < smallBlank; ++j) rowOfAns.add("");
            for (int j = 0; j < rowOfValues.size() - 1; ++j) {
                rowOfAns.add(rowOfValues.get(j));
                for (int k = 0; k < bigBlank; ++k) rowOfAns.add("");
            }
            rowOfAns.add(rowOfValues.get(rowOfValues.size() - 1));
            for (int j = 0; j < smallBlank; ++j) rowOfAns.add("");
            bigBlank = smallBlank;
            smallBlank = (smallBlank - 1) / 2;
            ans.add(rowOfAns);
        }
        return ans;
    }
}
学习笔记:
这是一道很繁琐的二叉树的题目。
先要找到规律,每个节点每一层的间隙是多大,发现间隙分为大间隙和小间隙还有推导公式后,开始用宽度优先遍历来写。
第一遍遍历无法完成,因为不知道二叉树深度到底有多大,只能将节点数值先存一下,第二次遍历再把空格填进去。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。