【每日一题】- 2019-09-04 - 655. Print Binary Tree #7

[watchpoints]

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/print-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[watchpoints]

扩展：

Print a tree and fill it to be complete tree， for example
10
1,2
-,-,-,3
-,-,-,-,-,-,6

[watchpoints]

树的高度含义：
https://link.zhihu.com/?target=https%3A//stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height

但是国内教科书上 树的高度是从1 开始的。

[watchpoints]

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func printTree(root *TreeNode) [][]string {

	rows := getHeight(root)
	cols := math.Pow(2, rows) - 1 // all nodes of tree

	var res [][]string //nil point
	for i := 0; i < int(rows); i++ {
		
		res = append(res, make([]string, int(cols)))
	}

	dfsPrintTree(root, 0, 0, int(cols)-1, res)

	return res

}

func dfsPrintTree(root *TreeNode, level int, start int, end int, res [][]string) {
	if root == nil || start > end {
		return
	}

	//print root
	mid := (start + end) / 2
	res[level][mid] = strconv.Itoa(root.Val)

	//print left subTree
	dfsPrintTree(root.Left, level+1, start, mid-1, res)
	//print right subTree
	dfsPrintTree(root.Right, level+1, mid+1, end, res)

}

//height of tree
func getHeight(root *TreeNode) float64 {
	if root == nil {
		return 0
	}
	left := getHeight(root.Left)
	rgiht := getHeight(root.Right)
	return math.Max(left, rgiht) + 1
}