由前序和中序重建二叉树

刺骨的言语ヽ痛彻心扉 2023-06-01 11:20 10阅读 0赞

### 笔试中二叉树遍历的题考的频率还是很高的，这里整理一下遍历的题~ ###

## ##

### 初始结构定义如下： ###

struct TreeNode 
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

### ① 由前序序列和中序序列重建二叉树 ###

递归 (数组左闭右开，m\_copy()函数右边是取不到值的，因为下标从0开始，到 size-1 结束)

vector<int> my_copy(vector<int> a, int left, int right)
    {
    	return vector<int> (a.begin()+left, a.begin()+right);
    }
    
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) 
    {
    	if(pre.size() == 0 || vin.size() == 0) 
    		return NULL;
    	TreeNode *node = new TreeNode(pre[0]);
    	for(int i = 0; i < vin.size(); i++)
    	{
    		if(pre[0] == vin[i])
    		{
    			node->left = reConstructBinaryTree(my_copy(pre, 1, i+1), my_copy(vin, 0, i));
    			node->right = reConstructBinaryTree(my_copy(pre, i+1, pre.size()), my_copy(vin, i+1, vin.size()));
    		}
    	}
    	return node;
    }

### ②由后序序列和中序序列重建二叉树 ###

vector<int> m_copy(vector<int> v, int l, int r)
    {
    	return vector<int> (v.begin()+l,v.begin+r);
    }
    
    TreeNode* reConstructBTree(vector<int> past, vector<int> vin)
    {
    	if(past.size() == 0 || vin.size() == 0)
    		return NULL;
    
    	TreeNode* node = new TreeNode(past[past.size()-1]);
    
    	for(int i = 0; i < vin.size(); ++i)
    	{
    		if(past[past.size()-1] == vin[i])
    		{
    			node->left = reConstructBTree(m_copy(past,0,i),m_copy(vin,0,i));
    			node->right = reConstructBTree(m_copy(past,i,past.size()-1),m_copy(vin,i+1,vin.size()));
    		}
    	}
    	return node;
    }