106. Construct Binary Tree from Inorder and Postorder Traversal Medium

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