Algorithm to Construct Binary Tree from Preorder and Inorder Tra

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

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) —

推荐阅读：
捶背作文150字　 蹇叔哭师原文及翻译　 百家讲坛系列节目《易中天品三国》MP3蓝奏云下载　 百家讲坛系列节目《国史通鉴（第一部）》蓝奏云mp3下载　 展喜犒师原文及翻译　 介之推不言禄原文及翻译　 寺人披见文公原文及翻译　 子鱼论战原文及翻译　 阴饴甥对秦伯原文及翻译　 诗词名句鉴赏：青青子衿，悠悠我心。　
评论列表
添加评论