Algorithm to Construct Binary Tree from Preorder and Inorder Tra

  • 时间：2020-09-23 15:11:59
  • 分类：网络文摘
  • 阅读：92 次

Given preorder and inorder traversal of a tree, construct the binary tree. You may assume that duplicates do not exist in the tree.

For example, given

1
2

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

How to Construct the Binary Tree using Divide-and-Conquer Algorithm?

The root element is located the first in a binary tree’s preorder. Thus, we can iterate the inorder to find the index of the root element, then, we know the left and right part of the inorder traversal. Then, going back to the preorder, we can also find the separation between left and right tree. Recursively, we can construct the left and right tree.

However, a first naive implementation is as follows C++, which is inefficient as the intermediate vectors are copied. And we have done some clumbsy work (remembering the left tree in the hash set) to find the separation point. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty() || inorder.empty()) return nullptr;    
        int n = preorder.size();
        // root is the first element of preorder
        TreeNode* root = new TreeNode(preorder[0]);
        // push elements to set before root in inorder
        int i = 0;
        unordered_set<int> inorder_left_set;        
        vector<int> inorder_left;
        while (i < n) {
            if (inorder[i] == root->val) break;
            inorder_left_set.insert(inorder[i]);
            inorder_left.push_back(inorder[i]);
            i ++;
        }
        // and the right part of the inorder
        vector<int> inorder_right;
        while (i < n) {
            inorder_right.push_back(inorder[i]);
            i ++;
        } 
        // now push all nodes in set to preorder left
        int j = 1;
        vector<int> preorder_left;
        while (j < n) {
            if (!inorder_left_set.count(preorder[j])) break;
            preorder_left.push_back(preorder[j]);
            j ++;
        }
        // the right tree of the preorder
        vector<int> preorder_right;
        while (j < n) {
            preorder_right.push_back(preorder[j]);
            j ++;
        }
        // recursively construct left tree        
        root->left = buildTree(preorder_left, inorder_left);
        // recursively construct right tree
        root->right = buildTree(preorder_right, inorder_right);
        return root;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty() || inorder.empty()) return nullptr;    
        int n = preorder.size();
        // root is the first element of preorder
        TreeNode* root = new TreeNode(preorder[0]);
        // push elements to set before root in inorder
        int i = 0;
        unordered_set<int> inorder_left_set;        
        vector<int> inorder_left;
        while (i < n) {
            if (inorder[i] == root->val) break;
            inorder_left_set.insert(inorder[i]);
            inorder_left.push_back(inorder[i]);
            i ++;
        }
        // and the right part of the inorder
        vector<int> inorder_right;
        while (i < n) {
            inorder_right.push_back(inorder[i]);
            i ++;
        } 
        // now push all nodes in set to preorder left
        int j = 1;
        vector<int> preorder_left;
        while (j < n) {
            if (!inorder_left_set.count(preorder[j])) break;
            preorder_left.push_back(preorder[j]);
            j ++;
        }
        // the right tree of the preorder
        vector<int> preorder_right;
        while (j < n) {
            preorder_right.push_back(preorder[j]);
            j ++;
        }
        // recursively construct left tree        
        root->left = buildTree(preorder_left, inorder_left);
        // recursively construct right tree
        root->right = buildTree(preorder_right, inorder_right);
        return root;
    }
};

A better implementation is as follows, based on the same algorithm. We define a helper function take takes 4 extra integer parameters to define the ranges of the traversal vectors – thus avoiding copying the vectors. Also, after finding the index of the root element in the inorder traversal, we can compute the number of nodes in the left tree, thus a quicker way to find the separation in the preorder traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
private:
    TreeNode* buildTree(vector<int>& preorder, int a, int b, vector<int>& inorder, int c, int d) {
        if (a > b) return nullptr;
        // root is the first element of preorder
        TreeNode* root = new TreeNode(preorder[a]);
        // find the root position in inorder
        int i = c;
        while (i <= d) {
            if (inorder[i] == root->val) break;
            i ++;
        }
        int leftcnt = i - c - 1;
        a ++;
        // recursively construct left tree        
        root->left = buildTree(preorder, a, a + leftcnt, inorder, c, c + leftcnt);
        // recursively construct right tree
        root->right = buildTree(preorder, a + leftcnt + 1, b, inorder, i + 1, d);
        return root;
    }    
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
private:
    TreeNode* buildTree(vector<int>& preorder, int a, int b, vector<int>& inorder, int c, int d) {
        if (a > b) return nullptr;
        // root is the first element of preorder
        TreeNode* root = new TreeNode(preorder[a]);
        // find the root position in inorder
        int i = c;
        while (i <= d) {
            if (inorder[i] == root->val) break;
            i ++;
        }
        int leftcnt = i - c - 1;
        a ++;
        // recursively construct left tree        
        root->left = buildTree(preorder, a, a + leftcnt, inorder, c, c + leftcnt);
        // recursively construct right tree
        root->right = buildTree(preorder, a + leftcnt + 1, b, inorder, i + 1, d);
        return root;
    }    
};

The time complexity is O(N) where N nodes will be visited once during the process of constructing the binary tree. You can also use the similar algorithm to convert to a binary tree from its’ postorder and inorder sequences: How to Construct Binary Tree from Inorder and Postorder Traversal using Depth First Search Algorithm (Recursion)?

Related Binary Tree Construction Algorithms

You may also like the following posts on the similar tree problems.

  • Recursive Algorithm to Construct Binary Tree from Preorder and Postorder Traversal
  • How to Construct Binary Search Tree from Preorder Traversal in Python?
  • Algorithm to Construct Binary Tree from Preorder and Inorder Traversal
  • How to Construct Binary Search Tree from Preorder Traversal? (C++ and Java)
  • How to Construct String from Binary Tree?
  • How to Balance a Binary Search Tree using Recursive Inorder Traversal Algorithm?
  • How to Construct the Maximum Binary Tree using Divide-and-Conquer Recursion Algorithm?
  • How to Construct Binary Tree from Inorder and Postorder Traversal using Depth First Search Algorithm (Recursion)?
  • How to Construct Binary Tree from String (Binary Tree Deserialization Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
A Microsoft Coding Interview Screening for Position Principal So　 The Brace Expansion Algorithms using Breadth First Search or Dep　 Coding Exercise: Sum of Digits in the Minimum Number　 Javascript Coding Exercise: The QuickSort Implementation in Java　 In-place Run-Length String Compressions using C++　 Algorithms to Compute the Factor Combinations for An Integer usi　 How and Why You Should Use Infographics On Your Blog　 How to Make Your “Contact Us” Page Kick Ass　 The A to Z of Content Marketing: Habits Every Content Marketer S　 Keeping the Flame Going: How to Rock a Steady Job and Still Have　
评论列表
添加评论