655.输出二叉树

链接：655.输出二叉树
难度：Medium
标签：树、深度优先搜索、广度优先搜索、二叉树
简介：返回构造得到的矩阵 res 。

题解 1 - rust

• 编辑时间：2022-08-22
• 内存消耗：2MB
• 编程语言：rust
• 解法介绍：dfs。

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn print_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<String>> {
        let height = Solution::get_height(root.as_ref()) - 1;
        let n = 2_usize.pow(height as u32 + 1) - 1;
        let mut ans = vec![vec![String::new(); n]; height + 1];
        let root = root.unwrap();
        Solution::dfs(root, &mut ans, height, 0, (n - 1) / 2);
        ans
    }
    fn get_height(node: Option<&Rc<RefCell<TreeNode>>>) -> usize {
        match node {
            Some(node) => {
                1 + Solution::get_height(node.borrow().left.as_ref())
                    .max(Solution::get_height(node.borrow().right.as_ref()))
            }
            None => 0,
        }
    }
    fn dfs(
        node: Rc<RefCell<TreeNode>>,
        data: &mut Vec<Vec<String>>,
        height: usize,
        r: usize,
        c: usize,
    ) {
        data[r][c] = format!("{}", node.borrow().val);
        if node.borrow().left.is_some() {
            Solution::dfs(
                node.borrow().left.clone().unwrap(),
                data,
                height,
                r + 1,
                c - 2_usize.pow((height - r - 1) as u32),
            )
        }
        if node.borrow().right.is_some() {
            Solution::dfs(
                node.borrow().right.clone().unwrap(),
                data,
                height,
                r + 1,
                c + 2_usize.pow((height - r - 1) as u32),
            )
        }
    }
}