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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| // @lc code=start
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
/// ## 解题思路
/// - 队列
/// 1. 首先计算树的最大深度;
/// 2. 根据最大深度,计算打印数组的长,宽, 根据长宽初始化打印数组;
/// 3. 根节点在数组中的位置为(0, width / 2), 将(root, r=0, left=0, right=width-1)四元组入队列;
/// 4. 依次取出队列中的四元组, 根据四元组值更新打印数组;
/// 5. 如果当前节点存在左子节点,右子节点加入到队列尾部;
pub fn print_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<String>> {
/// 获取二叉树的高度
fn get_heigh(root: Option<Rc<RefCell<TreeNode>>>) -> usize {
match root {
None => 0,
Some(node) => {
1 + std::cmp::max(
get_heigh(node.borrow().left.clone()),
get_heigh(node.borrow().right.clone()),
)
}
}
}
let heigh = get_heigh(root.clone());
let width = ((1 << heigh as u32) - 1) as usize;
let mut res = vec![vec!["".to_string(); width]; heigh];
if root.is_none() {
return res;
}
let mut q = VecDeque::new();
q.push_back((root.unwrap().clone(), 0, 0, width-1)); //将根节点push到队列尾部;
// 依次从队列头取出一个节点元组
while let Some((node, row, left, right)) = q.pop_front() {
let col = (left + right) / 2; //计算当前节点所在的col
res[row][col] = node.borrow().val.to_string(); //更新打印数组当前节点值
// 如果存在左子节点
if let Some(left_node) = node.borrow().left.as_ref() {
q.push_back((left_node.clone(), row+1, left, col-1)); //将左子节点push到队列尾
}
// 如果存在右子节点
if let Some(right_node) = node.borrow().right.as_ref() {
q.push_back((right_node.clone(), row+1, col+1, right)); //将右子节点push到队列尾
}
}
res
}
}
// @lc code=end
|
