递归法

• 把构建树可以转化成构建子树，递归法的基础
• 并没有完全想象出整个过程，大致写法+边界处理left<right
• C++使用索引+引用的方式，python可以直接选择数组

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型vector 
     * @param vinOrder int整型vector 
     * @return TreeNode类
     */
    TreeNode* recrusion(vector<int>& preOrder,vector<int>& vinOrder,int preleft,int preright,int vinleft,int vinright)
    {
        if(preleft>preright||vinleft>vinright)
        {
            return nullptr;
        }
        TreeNode* root=new TreeNode(preOrder[preleft]);
        int vinroot=vinleft;
        for(int i=vinleft;i<=vinright;i++)
        {
            if(vinOrder[i]==preOrder[preleft])
            {
                vinroot=i;
                break;
            }
        }
        int lenleft=vinroot-vinleft;
        int lenright=vinright-vinroot;
        root->left=recrusion(preOrder,vinOrder,preleft+1,preleft+lenleft,vinleft,vinroot-1);
        root->right=recrusion(preOrder,vinOrder,preleft+lenleft+1,preright,vinroot+1,vinright);
        return root;
    }
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        // write code here
        // 1  2 4 7  3 5 6 8
        // 4 7  2  1  5  3  8 6
        return recrusion(preOrder,vinOrder,0,preOrder.size()-1,0,vinOrder.size()-1);
    }
};

栈法 --待理解

• 树的前序遍历表示入栈，中序遍历表示出栈

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int n = pre.size();
        int m = vin.size();
        //每个遍历都不能为0
        if(n == 0 || m == 0) 
            return NULL;
        stack<TreeNode*> s;
        //首先建立前序第一个即根节点
        TreeNode *root = new TreeNode(pre[0]); 
        TreeNode *cur = root;
        for(int i = 1, j = 0; i < n; i++){
            //要么旁边这个是它的左节点
            if(cur->val != vin[j]){ 
                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;
    }
};