JZ7 重建二叉树

方法一：递归做法

前序的第一个结点就是根节点，而后在中序中将根节点的位置找出，根节点的左边是左子树，右边是右子树，而后再带入前序中分析，形成迭代。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size() == 0 || vin.size() == 0) return nullptr; //特殊情况和迭代终止条件

        TreeNode *root = new TreeNode(pre[0]);
        for(int i = 0; i < pre.size(); i ++ ){
            if(vin[i] == pre[0]){
                vector<int>leftpre(pre.begin() + 1, pre.begin() + i + 1);
                vector<int>leftvin(vin.begin(), vin.begin() + i);
                root->left = reConstructBinaryTree(leftpre, leftvin);
                vector<int>rightpre(pre.begin() + i + 1, pre.end());
                vector<int>rightvin(vin.begin() + i + 1, vin.end());
                root->right = reConstructBinaryTree(rightpre, rightvin);
                break;
            }
        }
        return root;
    }
};

• 时间复杂度：O(n)，即每个结点都遍历一次Unexpected text node: 'O(n)'O(n)，其中<span class="katex"><span class="katex-mathml"><span id="MathJax-Element-6-Frame" class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><merror><mtext>Unexpected text node: 'n'</mtext></merror></math>"><span id="MathJax-Span-41" class="math"><span id="MathJax-Span-42" class="mrow"><span id="MathJax-Span-43"><span id="null" class="merror"><span id="MathJax-Span-44" class="mrow"><span id="MathJax-Span-45" class="mtext">Unexpected text node: 'n'Unexpected text node: 'n'n为数组长度，即二叉树的节点数，构建每个节点进一次递归，递归中所有的循环加起来一共<span class="katex"><span class="katex-mathml"><span id="MathJax-Element-7-Frame" class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><merror><mtext>Unexpected text node: 'n'</mtext></merror></math>"><span id="MathJax-Span-46" class="math"><span id="MathJax-Span-47" class="mrow"><span id="MathJax-Span-48"><span id="null" class="merror"><span id="MathJax-Span-49" class="mrow"><span id="MathJax-Span-50" class="mtext">Unexpected text node: 'n'Unexpected text node: 'n'n次
• 空间复杂度：辅助数组和迭代栈都是n，递归栈最大深度不超过n,重建的二叉树空间是必要空间，不是辅助空间

方法二：

也可以用类似非递归前序遍历的方式建立二叉树，利用栈辅助进行非递归，然后依次建立节点。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int n = pre.size();
        int m = vin.size();
        if(n == 0 || m == 0) return nullptr;

        stack<TreeNode*> s;
        TreeNode *root = new TreeNode(pre[0]);
        TreeNode *cur = root;

        for(int i = 1, j = 0; i < pre.size(); i ++ ){
            if(vin[j] != cur->val)//pre数组中当前节点是上一个节点的左子树
            {
                cur->left = new TreeNode(pre[i]);
                s.push(cur);
                cur = cur->left;
            }
            else
            {
                j++;
                //当前节点是上一个节点的祖先的右子树
                while(!s.empty() && s.top()->val == vin[j]){
                    cur = s.top();
                    s.pop();
                    j ++ ;
                }
                //当前节点是上一个节点的右子树
                cur ->right = new TreeNode(pre[i]);
                cur = cur->right;
            }
        }
        return root;
    }
};