leetcode_construct_binary_tree_from_inorder_and_postorder_traversal

发表于

难度：Medium

解题思路：

      a
  b     c
d  e  f  g

中序遍历：d b e a f c g
后序遍历：d e b f g c a

可知：a一定是root，在中序遍历中，a的左侧即左子树，a的右侧为右子树，并可以分别计算出各自的长度。计算出长度后，可以在后序遍历中，找出左子树的后序遍历，右子树的后序遍历，进行递归。

代码如下：

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
/**
 * 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>& inorder, vector<int>& postorder) {
        return buildSubTree(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
    }
    TreeNode* buildSubTree(vector<int>& inorder, vector<int>& postorder, int in_left, int in_right, int post_left, int post_right)
    {
        if(in_left > in_right || post_left > post_right)
            return NULL;
        else if(in_left == in_right || post_left == post_right)
        {
            TreeNode* new_node = new TreeNode(postorder[post_right]);
            return new_node;
        }
        else
        {
            TreeNode* new_node = new TreeNode(postorder[post_right]);
            int i = in_left;
            for(; i <= in_right; i++)
            {
                if(inorder[i] == postorder[post_right])
                    break;
            }
            int new_position = i;
            int right_length = in_right-new_position;
            new_node->left = buildSubTree(inorder, postorder, in_left, new_position-1, post_left, post_right-right_length-1);
            new_node->right = buildSubTree(inorder, postorder, new_position+1, in_right, post_right-right_length, post_right-1);
            return new_node;
        }
    }
};

运行结果：49ms，超过18.17%