算法面试真题详解:输出二叉树-阿里云开发者社区

开发者社区> 算法编程> 正文

算法面试真题详解:输出二叉树

简介: 算法面试真题详解:输出二叉树

描述
按照以下规则在 m*n 二维字符串数组中打印二叉树:

  1. 行号m应该等于给定二叉树的高度。
  2. 列号n始终为奇数。
  3. 根节点的值(以字符串格式)应该放在它可以放入的第一行的正中间。根节点所属的列和行将剩余空间分成两部分(左下部分和右下部分)。您应该在左下部分打印左子树,并在右下部分打印右子树。左下部和右下部应具有相同的大小。即使一个子树为空,而另一个子树不为空,你也不需要打印空子树,但仍然需要留出与另外一个子树一样大的空间。但是,如果两个子树都为空,那么您不需要为它们留出空间。
  4. 每个未使用的空格应包含一个空字符串""。
  5. 按照相同的规则打印所有子树。
  6. 二叉树的高度在[1,10][1,10]范围内。

在线评测地址:领扣题库官网

样例1

输入:{1,2}
    1
   /
  2
输出:
 [["", "1", ""],
  ["2", "", ""]]

样例2

输入: {1,2,3,#,4}
    1
   / \
  2   3
   \
    4
输出:
 [["", "", "", "1", "", "", ""],
  ["", "2", "", "", "", "3", ""],
  ["", "", "4", "", "", "", ""]]

样例3:

输入:{1,2,5,3,#,#,#,4}
        1
       / \
      2   5
     / 
    3 
   / 
  4 
输出:
 [["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
  ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
  ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
  ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]

算法:DFS

算法思路

  • 输出到的矩阵的列数永远是奇数 -- 对于所有子树, 即原矩阵的子矩阵也是奇数. 因为是奇数时, 左右子树才能平分列数. 一棵高度为 height 的二叉树对应的矩阵是 height∗(2height−1)height∗(2height−1) 的.
  • 先 dfs 确定二叉树的高度, 然后定义字符串二维数组. 再次 dfs 把每一个节点的值填入二维数组即可. 第二次 dfs 的过程中需要记录以下信息:
  • 当前节点所在行, 列 -- 确定当前节点的值填入二维数组的哪个位置
  • 当前节点的子树的宽度 -- 确定该节点的左右子节点该填入的位置
  • 当前节点在 row, col, 宽度是 width 时, 其左右子树的宽度均为 width / 2 - 1 (宽度永远是奇数), 左右子节点所在列与 col 的距离相同, 都是宽度的一半.
  • 总归, 两次dfs就可以解决这个问题.

    public class Solution {
    /**
     * @param root: the given tree
     * @return: the binary tree in an m*n 2D string array
     */
    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> res = new LinkedList<>();
        int height = root == null ? 1 : getHeight(root);
        int rows = height, columns = (int) (Math.pow(2, height) - 1);
        List<String> row = new ArrayList<>();
        for (int i = 0; i < columns; i++) {
            row.add("");
        }
        for (int i = 0; i < rows; i++) {
            res.add(new ArrayList<>(row));
        }
        populateRes(root, res, 0, rows, 0, columns - 1);
        return res;
    }
    
    public void populateRes(TreeNode root, List<List<String>> res, int row, int totalRows, int i, int j) {
        if (row == totalRows || root == null) {
            return;
        }
        res.get(row).set((i + j) / 2, Integer.toString(root.val));
        populateRes(root.left, res, row + 1, totalRows, i, (i + j) / 2 - 1);
        populateRes(root.right, res, row + 1, totalRows, (i + j) / 2 + 1, j);
    }
    
    public int getHeight(TreeNode root) {
        if (root == null)
            return 0;
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }

    更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接