889. Construct Binary Tree from Preorder and Postorder Traversal Medium

1/**
2 * [889] Construct Binary Tree from Preorder and Postorder Traversal
3 *
4 * Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.
5 * If there exist multiple answers, you can return any of them.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2021/07/24/lc-prepost.jpg" style="width: 304px; height: 265px;" />
9 * Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
10 * Output: [1,2,3,4,5,6,7]
11 * 
12 * Example 2:
13 * 
14 * Input: preorder = [1], postorder = [1]
15 * Output: [1]
16 * 
17 *  
18 * Constraints:
19 * 
20 * 	1 <= preorder.length <= 30
21 * 	1 <= preorder[i] <= preorder.length
22 * 	All the values of preorder are unique.
23 * 	postorder.length == preorder.length
24 * 	1 <= postorder[i] <= postorder.length
25 * 	All the values of postorder are unique.
26 * 	It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.
27 * 
28 */
29pub struct Solution {}
30use crate::util::tree::{TreeNode, to_tree};
31
32// problem: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
33// discuss: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/?currentPage=1&orderBy=most_votes&query=
34
35// submission codes start here
36
37// Definition for a binary tree node.
38// #[derive(Debug, PartialEq, Eq)]
39// pub struct TreeNode {
40//   pub val: i32,
41//   pub left: Option<Rc<RefCell<TreeNode>>>,
42//   pub right: Option<Rc<RefCell<TreeNode>>>,
43// }
44// 
45// impl TreeNode {
46//   #[inline]
47//   pub fn new(val: i32) -> Self {
48//     TreeNode {
49//       val,
50//       left: None,
51//       right: None
52//     }
53//   }
54// }
55use std::rc::Rc;
56use std::cell::RefCell;
57impl Solution {
58    pub fn construct_from_pre_post(preorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
59        Some(Rc::new(RefCell::new(TreeNode::new(0))))
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_889() {
71    }
72}
73