C++ recursive DFS template for constructing binary tree


  • 0
    H

    Construct Binary Tree from Preorder and Inorder Traversal

    class Solution {
    public:
        unordered_map<int, int> um; // map inorder[i] to i
        TreeNode* dfs(vector<int>& preorder, int pleft, int pright, vector<int>& inorder, int ileft, int iright) {
            if(pleft > pright || ileft > iright) return nullptr;
            int root_val = preorder[pleft]; // leftmost element in preorder is the root node
            TreeNode* root = new TreeNode(root_val);
            
            int root_idx = um[root_val]; // root index in inorder
            int nleft = root_idx - ileft; // size of left sub-tree
            root->left = dfs(preorder, pleft+1, pleft + nleft, inorder, ileft, root_idx - 1);
            root->right = dfs(preorder, pleft + nleft + 1, pright, inorder, root_idx + 1, iright);
            return root;
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            int n = preorder.size(), i = 0;
            for(int val : inorder) um[val] = i ++;
            return dfs(preorder, 0, n-1, inorder, 0, n-1);
        }
    };
    

    Construct Binary Tree from Inorder and Postorder Traversal

    class Solution {
    public:
        unordered_map<int, int> um; // map inorder[i] to i
        TreeNode* dfs(vector<int>& inorder, int ileft, int iright, vector<int>& postorder, int pleft, int pright) {
            if(ileft > iright || pleft > pright) return nullptr;
            int root_val = postorder[pright]; // last element in postorder is the root node
            TreeNode* root = new TreeNode(root_val);
    
            int root_idx = um[val]; // root index in inorder
            int nleft = root_idx - ileft; // size of left sub-tree
            root->left = dfs(inorder, ileft, root_idx-1, postorder, pleft, pleft + nleft - 1);
            root->right = dfs(inorder, root_idx+1, iright, postorder, pleft + nleft, pright - 1);
            return root;
        }
        
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            int n = inorder.size(), i = 0;
            for(int val : inorder) um[val] = i++;
            return dfs(inorder, 0, n-1, postorder, 0, n-1);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.