LEETCODE 655. Print Binary Tree 解题思路分析

题目大意:

输出二叉树

在一个 m*n 的二维字符串数组中输出二叉树,并遵守以下规则:

  • 数 m 应当等于给定二叉树的高度。
  • 列数 n 应当总是奇数。
  • 根节点的值(以字符串格式给出)应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分(左下部分和右下部分)。你应该将左子树输出在左下部分,右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空,你不需要为空的子树输出任何东西,但仍需要为另一个子树留出足够的空间。然而,如果两个子树都为空则不需要为它们留出任何空间。
  • 每个未使用的空间应包含一个空的字符串””。
  • 使用相同的规则输出子树。

示例 1:

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

示例 2:

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

示例 3:

输入:
      1
     / \
    2   5
   / 
  3 
 / 
4 
输出:

[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
 ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
 ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
 ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]

注意: 二叉树的高度在范围 [1, 10] 中。


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=655

解题思路分析:

本题首先要确定出最后要打印的二维数组的高和宽,二维数组的高就是二叉树的高度,宽则是二叉树在满节点状态下的总节点个数,二叉树总节点个数的计算方法是2的m次方减一,其中m为二叉树高度。求二叉树高度可以使用bfs。

在确定了高和宽之后,我们再使用dfs描画每一条路径。dfs方法需要三个重要参数,当前行,当前列的左端和右端范围。dfs起始点为二叉树顶点,顶点一定在首行的中间位置,因此,此时当前行为0,当前列的范围是[left, n-1],其中left为0,n为总列数。当前列的范围中点mid即是顶点的所在位置。描画完顶点之后,如果其存在左子节点,那么将左节点递归至子问题,此时行数加一,列的范围变为[left, mid-1],同理,右子节点的范围应该是[mid+1, right]。循环此步骤直到描画完所有节点为止。

个人感觉这是一道同时练习bfs和dfs很好的题目。

实现代码:

public List<List<String>> printTree(TreeNode root) {
    int height = bfs(root); // 计算二叉树高度
    int width = (int)Math.pow(2, height) - 1; // 宽度
    // 返回结果
    List<List<String>> res = new ArrayList<>();
    for(int i=0;i<height;i++){
        List<String> list = new ArrayList<>();
        for(int j=0;j<width;j++){
            list.add("");
        }
        res.add(list);
    }
    // 递归描画每个节点
    dfs(root, 0, 0,width-1,res);
    return res;
}

int bfs(TreeNode root){
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    int height=0;
    while(q.size()>0){
        int size=q.size();
        while(size>0){
            size--;
            TreeNode n = q.poll();
            if(n.left!=null) q.offer(n.left);
            if(n.right!=null) q.offer(n.right);
        }
        height++;
    }
    return height;
}

void dfs(TreeNode root, int r, int left, int right, List<List<String>> res){
    int mid = (left+right)/2;
    res.get(r).set(mid, String.valueOf(root.val));
    if(root.left!=null){
        dfs(root.left, r+1, left, mid-1,res);
    }
    if(root.right!=null){
        dfs(root.right, r+1, mid+1, right,res);
    }
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 99.91% of Java online submissions for Print Binary Tree.

Memory Usage: 36.6 MB, less than 100.00% of Java online submissions for Print Binary Tree.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-655-print-binary-tree-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

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