【Java|golang】655. 输出二叉树----深度搜索以及确认深度

给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则：

树的 高度 为 height ，矩阵的行数 m 应该等于 height + 1 。
矩阵的列数 n 应该等于 2height+1 - 1 。
根节点 需要放置在 顶行 的 正中间 ，对应位置为 res[0][(n-1)/2] 。
对于放置在矩阵中的每个节点，设对应位置为 res[r][c] ，将其左子节点放置在 res[r+1][c-2height-r-1] ，右子节点放置在 res[r+1][c+2height-r-1] 。
继续这一过程，直到树中的所有节点都妥善放置。
任意空单元格都应该包含空字符串 “” 。
返回构造得到的矩阵 res 。

示例 1：

输入：root = [1,2]
输出：
[[“”,“1”,“”],
[“2”,“”,“”]]
示例 2：

输入：root = [1,2,3,null,4]
输出：
[[“”,“”,“”,“1”,“”,“”,“”],
[“”,“2”,“”,“”,“”,“3”,“”],
[“”,“”,“4”,“”,“”,“”,“”]]

提示：

树中节点数在范围 [1, 210] 内
-99 <= Node.val <= 99
树的深度在范围 [1, 10] 内

List<List<String>> res;
    int height;
    public List<List<String>> printTree(TreeNode root) {
       res=new ArrayList<>();
       height=0;
       getHeight(root,1);
       int bread=getPow(height)-1;
        for (int i = 0; i < height; i++) {
            List<String> rows=new ArrayList<>();
            for (int j = 0; j < bread; j++) {
                rows.add("");
            }
            res.add(rows);
        }
        dfs(root,1,(bread-1)/2);
        return res;
    }
    public int getPow(int mi){
        return (int) Math.pow(2,mi);
    }
    public void getHeight(TreeNode root,int currHeight){
        if(root==null){
            return;
        }
        if(currHeight>height){
            height=currHeight;
        }
        getHeight(root.left,currHeight+1);
        getHeight(root.right,currHeight+1);
    }
    public void dfs(TreeNode root,int row,int col){
         if (root==null){
             return;
         }
         List<String> rows = res.get(row - 1);
         rows.set(col,String.valueOf(root.val));
         dfs(root.left,row+1,col-getPow(height-row-1));
         dfs(root.right,row+1,col+getPow(height-row-1));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

var res [][]string
var height int
func printTree(root *TreeNode) [][]string {
    res =make([][]string,0)
    height=0
    getHeight(root,1)
    bread:=getPow(height)-1
	for i:=0;i<height ;i++  {
		rows :=make([]string,0)
		for j:=0;j<bread ;j++  {
			rows=append(rows,"")
		}
		res=append(res, rows)
	}
	dfs(root,1,(bread-1)/2)
    return res
}
func getHeight(root *TreeNode,currHeight int)  {
	if root==nil {
		return
	}
	if currHeight>height {
		height=currHeight
	}
	getHeight(root.Left,currHeight+1)
	getHeight(root.Right,currHeight+1)
}
func getPow(mi int) int {
	return int(math.Pow(2, float64(mi)))
}
func dfs(root *TreeNode,row,col int) {
	if root==nil {
		return
	}
	rows:=res[row-1]
	rows[col]=strconv.Itoa(root.Val)
	dfs(root.Left,row+1,col-getPow(height-row-1))
	dfs(root.Right,row+1,col+getPow(height-row-1))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39