广度优先搜索，深度优先搜索（前序 / 中序（含莫里斯） / 后序 遍历，递归和迭代（单栈 / 双栈）），''+ int / strconv.Itoa / Integer.toString / int.ToString / sprintf(char*, "%d", int) / to_string / str 将数字转为字符串，求解《655. 输出二叉树》
例题
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","","","",""]]
答案
广度优先搜索
var printTree = function(root) {
const m = bfs(root, q => {
const n = q.shift()
if (n.left) q.push(n.left)
if (n.right) q.push(n.right)
}) + 1, n = (1 << m) - 1, r = Array.from({length: m}, _ => new Array(n).fill(''))
bfs([root, n - 1 >>> 1], (q, depth) => {
const [n, c] = q.shift()
r[depth][c] = '' + n.val
if (n.left) q.push([n.left, c - (1 << m - depth - 2)])
if (n.right) q.push([n.right, c + (1 << m - depth - 2)])
})
return r
};
const bfs = (n, cb) => {
const q = [n]
let depth = -1
while (q.length) {
let l = q.length
depth++
while (l--) cb(q, depth)
}
return depth
}class Solution(object): # list 实现
def printTree(self, root):
m = self.getDepth(root) + 1
n = (1 << m) - 1
r = [[""] * n for _ in range(m)]
q, depth = [(root, n - 1 >> 1)], -1
while len(q):
l, depth = len(q), depth + 1
for _ in range(l):
n, c = q.pop(0)
r[depth][c] = str(n.val)
if n.left: q.append((n.left, c - (1 << m - depth - 2)))
if n.right: q.append((n.right, c + (1 << m - depth - 2)))
return r
def getDepth(self, n):
q, depth = [n], -1
while len(q):
l, depth = len(q), depth + 1
for _ in range(l):
n = q.pop(0)
if n.left: q.append(n.left)
if n.right: q.append(n.right)
return depthclass Solution(object): # deque 实现
def printTree(self, root):
m = self.getDepth(root) + 1
n = (1 << m) - 1
r = [[""] * n for _ in range(m)]
q, depth = deque([(root, n - 1 >> 1)]), -1
while len(q):
l, depth = len(q), depth + 1
for _ in range(l):
n, c = q.popleft()
r[depth][c] = str(n.val)
if n.left: q.append((n.left, c - (1 << m - depth - 2)))
if n.right: q.append((n.right, c + (1 << m - depth - 2)))
return r
def getDepth(self, n):
q, depth = deque([n]), -1
while len(q):
l, depth = len(q), depth + 1
for _ in range(l):
n = q.popleft()
if n.left: q.append(n.left)
if n.right: q.append(n.right)
return depth深度优先搜索 · 前序遍历 · 递归
var printTree = function(root) {
const m = d(root, 0), n = (1 << m) - 1, r = Array.from({length: m}, _ => new Array(n).fill(''))
root.c = n - 1 >>> 1
d(root, 0, (n, depth) => {
r[depth][n.c] = '' + n.val
if (n.left) n.left.c = n.c - (1 << m - depth - 2)
if (n.right) n.right.c = n.c + (1 << m - depth - 2)
})
return r
};
const d = (n, depth, cb) => {
if (n === null) return depth
if (cb) cb(n, depth)
return Math.max(d(n.left, depth + 1, cb), d(n.right, depth + 1, cb))
}function printTree(root: TreeNode | null): string[][] {
const m = getDepth(root, 0), n = (1 << m) - 1, r = Array.from({length: m}, _ => new Array(n).fill(''))
;(function d (n, depth, c) {
if (n === null) return
r[depth][c] = '' + n.val
d(n.left, depth + 1, c - (1 << m - depth - 2))
d(n.right, depth + 1, c + (1 << m - depth - 2))
})(root, 0, n - 1 >>> 1)
return r
};
const getDepth = (n, depth) => {
if (n === null) return depth
return Math.max(getDepth(n.left, depth + 1), getDepth(n.right, depth + 1))
}深度优先搜索 · 前序遍历 · 迭代
class Solution {
function printTree($root) {
$m = $this->getDepth($root) + 1;
$n = (1 << $m) - 1;
$r = array_fill(0, $m, array_fill(0, $n, ''));
$stack = [[$root, $n - 1 >> 1]];
while (count($stack)) {
list($n, $c) = array_pop($stack);
$r[$n->depth][$c] = '' . $n->val;
$t = 2 ** ($m - $n->depth - 2);
if ($n->right) $stack []= [$n->right, $c + $t];
if ($n->left) $stack []= [$n->left, $c - $t];
}
return $r;
}
function getDepth($n) {
$stack = [$n];
$n->depth = 0;
$depth = 0;
while (count($stack)) {
$n = array_pop($stack);
if ($n->right) {
$stack []= $n->right;
$depth = max($depth, $n->right->depth = $n->depth + 1);
}
if ($n->left) {
$stack []= $n->left;
$depth = max($depth, $n->left->depth = $n->depth + 1);
}
}
return $depth;
}
}深度优先搜索 · 中序遍历 · 递归
func printTree(root *TreeNode) [][]string {
m := getDepth(root, 0)
n := 1 << m - 1
r := make([][]string, m)
for i, _ := range r {
r[i] = make([]string, n)
}
var d func (n *TreeNode, depth int, c int)
d = func(n* TreeNode, depth int, c int) {
if n == nil {
return
}
t := int(math.Pow(2, float64(m - depth - 2)))
d(n.Left, depth + 1, c - t)
r[depth][c] = strconv.Itoa(n.Val)
d(n.Right, depth + 1, c + t)
}
d(root, 0, (n - 1) >> 1)
return r
}
func getDepth(n *TreeNode, depth int) int {
if n == nil {
return depth
}
return int(math.Max(float64(getDepth(n.Left, depth + 1)), float64(getDepth(n.Right, depth + 1))))
}深度优先搜索 · 中序遍历 · 单栈
class Solution {
class Pair {
TreeNode n;
int c;
public Pair(TreeNode n, int c) {
this.n = n;
this.c = c;
}
}
private Map<TreeNode, Integer> depths;
private int maxDepth = 0;
public List<List<String>> printTree(TreeNode root) {
int m = getDepth(root) + 1, n = (1 << m) - 1;
List<List<String>> r = new ArrayList<List<String>>(m);
for (int i = 0; i < m; i++) {
List<String> row = new ArrayList<String>(n);
for (int j = 0; j < n; j++) {
row.add("");
}
r.add(row);
}
Deque<Pair> stack = new ArrayDeque<Pair>();
Pair p = new Pair(root, n - 1 >> 1);
while (stack.isEmpty() == false || p.n != null) {
while (p.n != null) {
stack.push(p);
p = new Pair(p.n.left, p.c - (1 << m - depths.get(p.n) - 2));
}
Pair cur = stack.pop();
r.get(depths.get(cur.n)).set(cur.c, Integer.toString(cur.n.val));
p = new Pair(cur.n.right, cur.c + (1 << m - depths.get(cur.n) - 2));
}
return r;
}
public int getDepth(TreeNode n) {
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
depths = new HashMap<TreeNode, Integer>();
depths.put(n, 0);
TreeNode p = n;
while (stack.isEmpty() == false || p != null) {
while (p != null) {
stack.push(p);
updateDepth(p.left, p);
p = p.left;
}
TreeNode cur = stack.pop();
updateDepth(cur.right, cur);
p = cur.right;
}
return maxDepth;
}
public void updateDepth(TreeNode cur, TreeNode prev) {
if (cur != null && depths.containsKey(cur) == false) {
depths.put(cur, depths.get(prev) + 1);
maxDepth = Math.max(maxDepth, depths.get(cur));
}
}
}深度优先搜索 · 中序遍历 · 莫里斯
public class Solution {
private Dictionary<TreeNode, int> depths;
public IList<IList<string>> PrintTree(TreeNode root) {
int m = getDepth(root) + 1;
int n = (1 << m) - 1;
IList<IList<string>> r = new List<IList<string>>(m);
for (int i = 0; i < m; i++) {
IList<string> row = new List<string>(n);
for (int j = 0; j < n; j++) {
row.Add("");
}
r.Add(row);
}
Dictionary<TreeNode, int> cs = new Dictionary<TreeNode, int>();
cs.Add(root, n - 1 >> 1);
while (root != null) {
int depth = depths[root];
int c = cs[root];
TreeNode next = null;
if (root.left != null) {
TreeNode p = root.left;
while (p.right != null && p.right != root) p = p.right;
if (p.right == null) {
c -= 1 << m - depth - 2;
next = root.left;
p.right = root;
root = root.left;
} else {
r[depth][c] = root.val.ToString();
c += 1 << m - depth - 2;
next = root.right;
p.right = null;
root = root.right;
}
} else {
r[depth][c] = root.val.ToString();
c += 1 << m - depth - 2;
next = root.right;
root = root.right;
}
if (next != null && cs.ContainsKey(next) == false) cs.Add(next, c);
}
return r;
}
public int getDepth(TreeNode root) {
depths = new Dictionary<TreeNode, int>();
depths.Add(root, 0);
int depth = 0;
while (root != null) {
TreeNode prev = root;
if (root.left != null) {
TreeNode p = root.left;
while (p.right != null && p.right != root) p = p.right;
if (p.right == null) {
p.right = root;
root = root.left;
} else {
p.right = null;
root = root.right;
}
} else {
root = root.right;
}
if (root != null && depths.ContainsKey(root) == false) {
depths.Add(root, depths[prev] + 1);
depth = Math.Max(depth, depths[root]);
}
}
return depth;
}
}深度优先搜索 · 后序遍历 · 递归
#define MAX(a, b) a > b ? a : b
int getDepth(struct TreeNode* n, int depth){
if (n == NULL) return depth;
return MAX(getDepth(n->left, depth + 1), getDepth(n->right, depth + 1));
}
void d(struct TreeNode* n, int depth, int c, int* m, char*** r) {
if (n->left) d(n->left, depth + 1, c - (1 << *m - depth - 2), m, r);
if (n->right) d(n->right, depth + 1, c + (1 << *m - depth - 2), m , r);
sprintf(r[depth][c], "%d", n->val);
}
char *** printTree(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
int m = getDepth(root, 0), n = (1 << m) - 1;
char*** r = malloc(sizeof(char**) * m);
for (int i = 0; i < m; i++) {
char** row = malloc(sizeof(char*) * n);
for (int j = 0; j < n; j++) {
row[j] = malloc(sizeof(char) * 4);
row[j][0] = '\0';
}
r[i] = row;
}
d(root, 0, n - 1 >> 1, &m, r);
*returnSize = m;
*returnColumnSizes = malloc(sizeof(int *) * m);
for (int i = 0; i < m; i++) {
(*returnColumnSizes)[i] = n;
}
return r;
}深度优先搜索 · 后序遍历 · 递归 · 单栈
class Solution {
private:
unordered_map<TreeNode*, int> depths;
unordered_map<TreeNode*, int> cs;
int depth = 0;
public:
vector<vector<string>> printTree(TreeNode* root) {
int m = getDepth(root) + 1, n = (1 << m) - 1;
vector<vector<string>> r(m, vector<string>(n, ""));
stack<TreeNode*> st;
TreeNode* p = root;
TreeNode* prev = nullptr;
cs.emplace(p, (n - 1) >> 1);
while (st.empty() == false || p) {
while (p) {
st.push(p);
updateC(p->left, p, -1, &m);
p = p->left;
}
TreeNode* n = st.top();
st.pop();
if (n->right == nullptr || n->right == prev) {
r[depths[n]][cs[n]] = to_string(n->val);
prev = n;
} else {
st.push(n);
updateC(n->right, n, 1, &m);
p = n->right;
}
}
return r;
}
int getDepth(TreeNode* n) {
stack<TreeNode*> st;
TreeNode* p = n;
TreeNode* prev = nullptr;
depths.emplace(n, 0);
while (st.empty() == false || p) {
while (p) {
st.push(p);
updateDepth(p->left, p);
p = p->left;
}
TreeNode* n = st.top();
st.pop();
if (n->right == nullptr || n->right == prev) {
prev = n;
} else {
st.push(n);
updateDepth(n->right, n);
p = n->right;
}
}
return depth;
}
void updateDepth(TreeNode* cur, TreeNode* prev) {
if (cur != nullptr && depths.find(cur) == depths.end()) {
depths.emplace(cur, depths[prev] + 1);
depth = max(depth, depths[cur]);
}
}
void updateC(TreeNode* cur, TreeNode* prev, int c, int* m) {
if (cur != nullptr && cs.find(cur) == cs.end()) cs.emplace(cur, cs[prev] + c * (1 << (*m - depths[prev] - 2)) );
}
};深度优先搜索 · 后序遍历 · 递归 · 双栈
class Solution:
def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
self.depths, self.depth, self.cs = dict(), 0, dict()
m = self.getDepth(root) + 1
n = (1 << m) - 1
r = [[""] * n for _ in range(m)]
self.cs[root] = n - 1 >> 1
stack, outStack = [root], []
while len(stack):
n = stack.pop()
outStack.append(n)
if n.left:
self.updateC(n.left, n, -1)
stack.append(n.left)
if n.right:
self.updateC(n.right, n, 1)
stack.append(n.right)
while len(outStack):
n = outStack.pop()
r[self.depths[n]][self.cs[n]] = str(n.val)
return r
def getDepth(self, n: Optional[TreeNode]) -> int:
self.depths[n] = 0
stack = [n]
while len(stack):
n = stack.pop()
if n.left:
self.updateDepth(n.left, n)
stack.append(n.left)
if n.right:
self.updateDepth(n.right, n)
stack.append(n.right)
return self.depth
def updateDepth(self, cur: Optional[TreeNode], prev: TreeNode):
if cur != None and cur not in self.depths:
self.depths[cur] = self.depths[prev] + 1
self.depth = max(self.depth, self.depths[cur])
def updateC(self, cur: Optional[TreeNode], prev: TreeNode, c: int):
if cur != None and cur not in self.cs:
self.cs[cur] = self.cs[prev] + c * (1 << self.depth - self.depths[prev] - 1)