从中序与后序遍历构造二叉树

题目：

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

提示：

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length

• preorder 和 inorder 均 无重复 元素

思路：

首先，找出整棵树的根节点，即后序遍历的最后一个节点；定位到中序遍历中，根据根节点把中序遍历分为左右子树两部分，同时根据左右子树的大小把后序遍历也分为两部分，与之对应。找到左右子树的根节点，让根节点指向左右子树的根节点，直至子树为空。

版本1：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* root = NULL;
    void SearchRootofTree(vector<int> inorder, vector<int> postorder, TreeNode* parent, bool flag)
    {
        if(0 == inorder.size()) return;
        TreeNode* subtree_root = new TreeNode(postorder[postorder.size() - 1]);
        auto iter = find(inorder.begin(), inorder.end(), subtree_root->val);
        if(NULL == root) 
        {
            root = subtree_root;
        }
        else
        {
            if(flag)
            {
                parent->left = subtree_root;
            }
            else  
            {
                parent->right = subtree_root;
            }   
        }
        int size = iter - inorder.begin();
        SearchRootofTree(vector<int>(inorder.begin(), iter), vector<int>(postorder.begin(), postorder.begin() + size), subtree_root, true);
        SearchRootofTree(vector<int>(iter + 1, inorder.end()), vector<int>(postorder.begin() + size, postorder.end() - 1), subtree_root, false);
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        SearchRootofTree(inorder, postorder, NULL, true);
        return root;
    }
};

版本2：

class Solution {
public:
    TreeNode* SearchRootofTree(vector<int>& inorder, int left_inorder, int right_inorder, vector<int>& postorder, int left_postorder, int right_postorder)
    {
        if(0 == (right_inorder - left_inorder)) return NULL;
        TreeNode* subtree_root = new TreeNode(postorder[right_postorder - 1]);
        auto iter = find(inorder.begin() + left_inorder, inorder.begin() + right_inorder, subtree_root->val);   
        int size = iter - inorder.begin() - left_inorder;
        subtree_root->left = SearchRootofTree(inorder, left_inorder, iter - inorder.begin(), postorder, left_postorder, left_postorder + size);
        subtree_root->right = SearchRootofTree(inorder, iter - inorder.begin() + 1, right_inorder, postorder, left_postorder + size, right_postorder - 1);
        return subtree_root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        return SearchRootofTree(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};

题目：

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

思路1：

采用和上述题目一致的想法，不同的是先序队列的第一个元素是子树的根节点

class Solution {
public:
    TreeNode* SearchRootofTree(vector<int>& inorder, int left_inorder, int right_inorder, vector<int>& preorder, int left_preorder, int right_preorder)
    {
        if(0 == (right_inorder - left_inorder)) return NULL;
        TreeNode* subtree_root = new TreeNode(preorder[left_preorder]);
        auto iter = find(inorder.begin() + left_inorder, inorder.begin() + right_inorder, subtree_root->val);   
        int size = iter - inorder.begin() - left_inorder;
        subtree_root->left = SearchRootofTree(inorder, left_inorder, iter - inorder.begin(), preorder, left_preorder + 1, left_preorder + 1 + size);
        subtree_root->right = SearchRootofTree(inorder, iter - inorder.begin() + 1, right_inorder, preorder, left_preorder + 1 + size, right_preorder);
        return subtree_root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        return SearchRootofTree(inorder, 0, inorder.size(), preorder, 0, preorder.size());
    }
};

*思路2：

利用前序队列的特殊性，即后一个元素是前一个元素的左孩子，或者是前一个元素的右孩子，或前一个元素某个祖先的右孩子。怎样确定呢？根据中序队列进行判定。

• 我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（前序遍历的第一个节点），指针指向中序遍历的第一个节点；

• 我们依次枚举前序遍历中除了第一个节点以外的每个节点。如果 index 恰好指向栈顶节点，那么我们不断地弹出栈顶节点并向右移动 index，并将当前节点作为最后一个弹出的节点的右儿子；如果 index 和栈顶节点不同，我们将当前节点作为栈顶节点的左儿子；

• 无论是哪一种情况，我们最后都将当前的节点入栈。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        TreeNode* root = new TreeNode(preorder[0]);
        int index = 0;
        stack<TreeNode*> s;
        s.push(root);
        for(int i = 1; i < preorder.size(); ++i)
        {
            TreeNode* node = s.top();
            if(!s.empty() && node->val != inorder[index])
            {
                node->left = new TreeNode(preorder[i]);
                s.push(node->left);
            }
            else
            {
                while(inorder[index]!=preorder[i])          //判别条件有问题
                {
                    node = s.top();
                    s.pop();
                    index++;
                }
                node->right = new TreeNode(preorder[i]);
                s.push(node->right);
            }
        }
        return root;
    }
};

这个版本是错误的，需要考虑不一样的判别条件，如下：

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        TreeNode* root = new TreeNode(preorder[0]);
        int index = 0;
        stack<TreeNode*> s;
        s.push(root);
        for(int i = 1; i < preorder.size(); ++i)
        {
            TreeNode* node = s.top();
            if(node->val != inorder[index])
            {
                node->left = new TreeNode(preorder[i]);
                s.push(node->left);
            }
            else
            {
                while(!s.empty() && s.top()->val == inorder[index])
                {
                    node = s.top();
                    s.pop();
                    index++;
                }
                node->right = new TreeNode(preorder[i]);
                s.push(node->right);
            }
        }
        return root;
    }
};