use crate::share::TreeNode;
use std::cell::{Ref, RefCell};
use std::cmp::max;
use std::rc::Rc;

struct Solution {}
impl Solution {
    pub fn print_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<String>> {
        let height = Self::height(root.clone());
        //        println!("height is {}", height);
        Self::print_tree_internal(root, height)
    }
    fn print_tree_internal(root: Option<Rc<RefCell<TreeNode>>>, height: i32) -> Vec<Vec<String>> {
        let val = if root.is_none() {
            String::from("")
        } else {
            format!("{}", root.clone().unwrap().borrow().val)
        };

        if height == 1 {
            return vec![vec![String::from(val)]];
        }
        /*
        先凑出我这一层
        */
        let mut result = Vec::new();
        let space_count = (1 << (height - 1)) - 1;
        //        println!("height={},space_count={}", height, space_count);
        let mut this_level = Vec::new();
        for x in 0..space_count {
            this_level.push(String::from(""))
        }
        this_level.push(val);
        for x in 0..space_count {
            this_level.push(String::from(""))
        }
        result.push(this_level);
        let (leftNode, rightNode) = if root.is_none() {
            (None, None)
        } else {
            (
                root.clone().unwrap().borrow().left.clone(),
                root.clone().unwrap().borrow().right.clone(),
            )
        };
        let left = Self::print_tree_internal(leftNode, height - 1);
        let right = Self::print_tree_internal(rightNode, height - 1);
        //将左右拼接起来,保证宽度
        for i in 0..left.len() {
            let mut v = Vec::new();
            v.extend_from_slice(&left[i]);
            v.push(String::from(""));
            v.extend_from_slice(&right[i]);
            result.push(v);
        }
        result
    }
    fn height(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if root.is_none() {
            return 0;
        }
        let r = root.unwrap();
        let left = Self::height(r.borrow().left.clone());
        let height = Self::height(r.borrow().right.clone());
        return max(left, height) + 1;
    }
}
#[cfg(test)]
mod test {
    use super::*;
    use crate::share::*;
    #[test]
    fn test_find_duplcates_tree() {
        let t = build_tree_ignore_parent(&vec![1, 2, 3, null, 4]);
        assert_eq!(
            Solution::print_tree(t),
            vec![
                vec!["", "", "", "1", "", "", ""],
                vec!["", "2", "", "", "", "3", ""],
                vec!["", "", "4", "", "", "", ""]
            ]
        )
    }
}