105. Construct Binary Tree from Preorder and Inorder Traversal - cocoder39/coco39_LC GitHub Wiki

105. Construct Binary Tree from Preorder and Inorder Traversal

2020 Notes:

  1. first element of preorder is root
  2. left side of root in inorder are nodes in left sub tree
  3. based on #2, we get the size of left sub tree, then we can figure out the range of left sub tree nodes in preorder 
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
            return None
        
        n = len(preorder)
        num_to_inorder_idx = {inorder[i]: i for i in range(n)}
        
        def helper(preorder_start, preorder_end, inorder_start, inorder_end):
            if preorder_start > preorder_end:
                return None
            
            root_inorder_idx = num_to_inorder_idx[preorder[preorder_start]]
            num_left_node = root_inorder_idx - inorder_start
            left_preorder_end = preorder_start + num_left_node
            
            cur = TreeNode(preorder[preorder_start])
            cur.left = helper(preorder_start+1, left_preorder_end, inorder_start, root_inorder_idx-1)
            cur.right = helper(left_preorder_end+1, preorder_end, root_inorder_idx+1, inorder_end)
            
            return cur
        
        
        return helper(0, n-1, 0, n-1)

================================================================================================

pre_start index the root of tree, use it to divide the inorder[in_start ... in_end] into two part, front of root is left subtree and behind root is right subtree

  1. why time is O(n)? run helper() once build a node
  2. terminal condition is determined by int rootVal = preorder[preStart], where preorder[preStart] must be valid

O(n) time and O(n) space (including map and call stack)

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int sz = preorder.size();
        unordered_map<int, int> mp;
        for (int i = 0; i < sz; i++) {
            mp[inorder[i]] = i;
        }
        return helper(preorder, 0, sz - 1, inorder, 0, sz - 1, mp);
    }
    
    TreeNode* helper(vector<int>& preorder, int preStart, int preEnd, vector<int>& inorder, int inStart, int inEnd, unordered_map<int, int>& mp) {
        if (preStart > preEnd) {
            return nullptr;
        }
        
        int rootVal = preorder[preStart]; //validate it
        int rootInIdx = mp[rootVal];
        int leftPreStart = preStart + 1, leftPreEnd = rootInIdx - 1 - inStart + leftPreStart; 
        
        TreeNode* root = new TreeNode(rootVal);
        root->left = helper(preorder, leftPreStart, leftPreEnd, inorder, inStart, rootInIdx-1, mp);
        root->right = helper(preorder, leftPreEnd + 1, preEnd, inorder, rootInIdx + 1, inEnd, mp);
        return root;
    }
};
⚠️ **GitHub.com Fallback** ⚠️