1
2

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

1
2

输入：n = 1
输出：[[1]]

 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

// @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::rc::Rc;
impl Solution {
    /// ## 解题思路
    /// - 递归
    pub fn generate_trees2(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        if n == 0 {
            return Vec::new();
        }

        fn generate(start: i32, end: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
            if start > end {
                return vec![None];
            }

            let mut res = Vec::new();
            for i in start..=end {
                let left_trees = generate(start, i - 1);
                let right_trees = generate(i + 1, end);
                for l in &left_trees {
                    for r in &right_trees {
                        let current_tree = Some(Rc::new(RefCell::new(TreeNode::new(i))));
                        current_tree.as_ref().unwrap().borrow_mut().left = l.clone();
                        current_tree.as_ref().unwrap().borrow_mut().right = r.clone();
                        res.push(current_tree)
                    }
                }
            }

            res
        }

        generate(1, n)
    }
}
// @lc code=end