1028. Recover a Tree From Preorder Traversal Hard

1/**
2 * [1028] Recover a Tree From Preorder Traversal
3 *
4 * We run a preorder depth-first search (DFS) on the root of a binary tree.
5 * At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node.  If the depth of a node is D, the depth of its immediate child is D + 1.  The depth of the root node is 0.
6 * If a node has only one child, that child is guaranteed to be the left child.
7 * Given the output traversal of this traversal, recover the tree and return its root.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2019/04/08/recover-a-tree-from-preorder-traversal.png" style="width: 320px; height: 200px;" />
11 * Input: traversal = "1-2--3--4-5--6--7"
12 * Output: [1,2,5,3,4,6,7]
13 * 
14 * Example 2:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2019/04/11/screen-shot-2019-04-10-at-114101-pm.png" style="width: 256px; height: 250px;" />
16 * Input: traversal = "1-2--3---4-5--6---7"
17 * Output: [1,2,5,3,null,6,null,4,null,7]
18 * 
19 * Example 3:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2019/04/11/screen-shot-2019-04-10-at-114955-pm.png" style="width: 276px; height: 250px;" />
21 * Input: traversal = "1-401--349---90--88"
22 * Output: [1,401,null,349,88,90]
23 * 
24 *  
25 * Constraints:
26 * 
27 * 	The number of nodes in the original tree is in the range [1, 1000].
28 * 	1 <= Node.val <= 10^9
29 * 
30 */
31pub struct Solution {}
32use crate::util::tree::{TreeNode, to_tree};
33
34// problem: https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/
35// discuss: https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39// Definition for a binary tree node.
40// #[derive(Debug, PartialEq, Eq)]
41// pub struct TreeNode {
42//   pub val: i32,
43//   pub left: Option<Rc<RefCell<TreeNode>>>,
44//   pub right: Option<Rc<RefCell<TreeNode>>>,
45// }
46// 
47// impl TreeNode {
48//   #[inline]
49//   pub fn new(val: i32) -> Self {
50//     TreeNode {
51//       val,
52//       left: None,
53//       right: None
54//     }
55//   }
56// }
57use std::rc::Rc;
58use std::cell::RefCell;
59impl Solution {
60    pub fn recover_from_preorder(traversal: String) -> Option<Rc<RefCell<TreeNode>>> {
61        Some(Rc::new(RefCell::new(TreeNode::new(0))))
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_1028() {
73    }
74}
75