1
2

输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

1
2

输入: preorder = [1], postorder = [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
57
58
59
60

// @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 {
    /// ## 解题思路
    /// - 递归
    /// 1. 前序遍历： 根->左子树->右子树
    ///    后序遍历:  左子树->右子树->根
    /// 2. 所以数组的首尾为树的根，
    ///    preorder的[1]和postorder的[len-1]分别为两种左子树+右子树；
    /// 3. 每个子树的preorder slice第一个元素为左子树root，其必定在postorder的左子树最后；
    /// 4. 据此查找该子树根在postorder中的index，来将左右子树进划分；
    /// 5. 递归求出左右子树；
    pub fn construct_from_pre_post(
        preorder: Vec<i32>,
        postorder: Vec<i32>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        assert!(preorder.len() > 0);

        let root_val = preorder[0];
        let mut root = TreeNode::new(root_val);
        let len = preorder.len();
        // 元素个数小于2个
        if preorder.len() <= 1 {
            return Some(Rc::new(RefCell::new(root)));
        }

        let cut_idx = postorder.iter().position(|&x| x == preorder[1]).unwrap() + 1;
        let pre_left = &preorder[1..(cut_idx + 1)];
        let post_left = &postorder[0..cut_idx];
        root.left = Solution::construct_from_pre_post(pre_left.to_vec(), post_left.to_vec());

        if cut_idx < preorder.len() - 1 {
            let pre_right = &preorder[(cut_idx + 1)..len];
            let post_right = &postorder[cut_idx..len - 1];
            root.right = Solution::construct_from_pre_post(pre_right.to_vec(), post_right.to_vec());
        }

        Some(Rc::new(RefCell::new(root)))
    }
}
// @lc code=end