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

推荐阅读：
台湾三立新闻台直播「高清」　 台湾年代新闻台直播「高清」　 台湾非凡新闻台直播「高清」　 耀才财经台直播「流畅」　 香港亚太第一卫视ONE-TV直播　 凤凰卫视电影台直播_凤凰电影台直播观看　 TVB无线财经·资讯台直播观看【高清】　 TVB无线新闻台直播观看【高清】　 澳亚卫视直播「高清」　 澳门澳视体育台直播「高清」　
评论列表
添加评论