LeetCode Entry

889. Construct Binary Tree from Preorder and Postorder Traversal

23.02.2025 medium 2025 kotlin rust

Tree from preorder & postorder

889. Construct Binary Tree from Preorder and Postorder Traversal medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/904

Problem TLDR

Tree from preorder & postorder #medium #stack

Intuition

Follow the preorder. The tricky part is null detection:

• we can track that all values are to the left of the postorder index
• or, more clever from u/lee215/: when preorder meets postorder we are done in the current subtree

Approach

• we can slice arrays for subtrees; the interesting fact is preorder index as at most 2 positions right to the postorder and lengths are always equal
• Rust type evaluation is broken: it didn’t see the push and stops on the first get

Complexity

• Time complexity: \(O(n^2)\) for index search ans slicing, O(n) for the pre[i] == post[i] check

• Space complexity: \(O(n)\)

Code

    fun constructFromPrePost(pre: IntArray, post: IntArray): TreeNode? =
        if (pre.size < 1) null else TreeNode(pre[0]).apply { if (pre.size > 1) {
            val l = pre.size - 1; val j = post.indexOf(pre[1]) + 1;
            left = constructFromPrePost(pre.sliceArray(1..j), post.sliceArray(0..j))
            right = constructFromPrePost(pre.sliceArray(j + 1..l), post.sliceArray(j..<l))
        }}

    pub fn construct_from_pre_post(pre: Vec<i32>, post: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut s = vec![]; let mut j = 0;
        for v in pre {
            let n = Some(Rc::new(RefCell::new(TreeNode::new(v)))); if s.len() < 1 { s.push(n.clone()); continue }
            while s.last().and_then(|x| x.as_ref()).is_some_and(|x| x.borrow().val == post[j]) { s.pop(); j += 1 }
            if let Some(mut l) = s.last_mut().and_then(|x| x.as_mut()).map(|x| x.borrow_mut()){
                if l.left.is_none() { l.left = n.clone() } else { l.right = n.clone() }}
            s.push(n.clone());
        }; s[0].clone()
    }

    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post, int* i = new int(0), int* j = new int(0)) {
        TreeNode* n = new TreeNode(pre[(*i)++]);
        if (n->val != post[*j]) n->left = constructFromPrePost(pre, post, i, j);
        if (n->val != post[*j]) n->right = constructFromPrePost(pre, post, i, j);
        (*j)++; return n;
    }