Java实现 LeetCode 655 输出二叉树（DFS+二分）

谁借莪１个温暖的怀抱￠ 2023-07-21 06:15 5阅读 0赞

## 655. 输出二叉树 ##

在一个 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\] 中。

PS:  
先判断数组大小  
DFS+二分填充

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
     public List<List<String>> printTree(TreeNode root) { 
            if (root == null) { 
                return new ArrayList<>(1);
            }
            //先获取数组大小
            int depth = getDepth(root);
            int width = (int)(Math.pow(2, depth) - 1);
            width = width > 0 ? width : 1;
            String[][] result = new String[depth][width];
            List<List<String>> res = new LinkedList<>();
            //填充操作
            fill(result, 0, 0, width - 1, root);
            for (int i = 0; i < result.length; i++) { 
                LinkedList<String> linkedList = new LinkedList<>();
                for (int j = 0; j < result[i].length; j++) { 
                    if (result[i][j] == null) { 
                        linkedList.add("");
                    } else { 
                        linkedList.add(result[i][j]);
                    }
                }
                res.add(linkedList);
            }
            return res;
        }
    
        public void fill(String[][] ints, int depth, int start, int end, TreeNode node) { 
            if (node == null) { 
                return;
            }
            int mid = (start + end) / 2;
            ints[depth][mid] = String.valueOf(node.val);
            fill(ints, depth + 1, start, mid - 1, node.left);
            fill(ints, depth + 1, mid + 1, end, node.right);
        }
    
        public int getDepth(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            int left = getDepth(root.left) + 1;
            int right = getDepth(root.right) + 1;
            return right > left ? right : left;
        }
    }