Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal.png

解題思路 ：

利用 post-order 的尾端找到 root 的值 再用 root 值去 inorder 找到 root 在 inorder 中的 index 接著用 inorder 的頭到 index -1 的範圍當作左子數的範圍 index + 1 到 index 尾的範圍當右邊子樹的範圍繼續 recursive 注意在 recursive 裡面修改 postorder 檢查範圍的地方 要用到 inorder 的 root 跟兩邊的距離來算

C++ code :

<pre><code>
/**

• Definition of TreeNode:
• class TreeNode {
• public:

• int val;
  

• TreeNode *left, *right;
  

• TreeNode(int val) {
  

•     this->val = val;
  

•     this->left = this->right = NULL;
  

• }
  

• }
  */

class Solution {

/**
 *@param inorder : A list of integers that inorder traversal of a tree
 *@param postorder : A list of integers that postorder traversal of a tree
 *@return : Root of a tree
 */

public:

int getIndex(vector<int> &v, int target)
{
    for(int i = 0; i < v.size(); i++)
    {
        if(v[i] == target) return i;
    }
    return -1;
}


TreeNode *build(vector<int> &IN, int istart, int iend, vector<int> &POST, int pstart, int pend )
{
    if(istart > iend || pstart > pend) return nullptr;
    int root_val = POST[pend];
    int index = getIndex(IN, root_val);
    TreeNode *root = new TreeNode(root_val);
    root->left = build(IN, istart, index - 1, POST, pstart, pstart + (index - istart) - 1);
    root->right = build(IN, index + 1, iend, POST, pstart + (index - istart), pend - 1);
    return root;
}

TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
    // write your code here
    int iend = inorder.size() - 1;
    int pend = postorder.size() -1;
    return build(inorder, 0, iend, postorder, 0, pend);
}

};