力扣（LeetCode）算法_C++——重建二叉树

不念不忘少年蓝@ 2022-11-05 00:43 108阅读 0赞

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = \[3,9,20,15,7\]  
中序遍历 inorder = \[9,3,15,20,7\]  
返回如下的二叉树：

![在这里插入图片描述][20210303144404302.png]

限制：

0 <= 节点个数 <= 5000

class ListNode
    {
        
    public:
    	int val;
    	ListNode* next;
    	ListNode(int x) {
        
    		val = x; 
    		next = nullptr;
    	}
    };
    
    int* reversePrint(ListNode* head)
    {
        
    	stack<ListNode*> stacks;
    	ListNode* temp = head;
    	while (temp!=nullptr)
    	{
        
    		stacks.push(temp);
    		temp = temp->next;
    	}
    
    	int size = stacks.size();
    	int* prints = new int[size];
    	for (int i=0;i<size;i++)
    	{
        
    		prints[i] = stacks.top()->val;
    		stacks.pop();
    	}
    	return prints;
    }
    
    struct TreeNode {
        
    	int val;
    	TreeNode* left;
    	TreeNode* right;
    	TreeNode(int x) : val(x), left(NULL), right(NULL) {
        }
    };
    
    
    class Solution {
        
    private:
    	unordered_map<int, int> index;
    
    public:
    	TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        
    		if (preorder_left > preorder_right) {
        
    			return nullptr;
    		}
    
    		// 前序遍历中的第一个节点就是根节点
    		int preorder_root = preorder_left;
    
    		// 在中序遍历中定位根节点
    		int inorder_root = index[preorder[preorder_root]];
    
    		// 先把根节点建立出来
    		TreeNode* root = new TreeNode(preorder[preorder_root]);
    		// 得到左子树中的节点数目
    		int size_left_subtree = inorder_root - inorder_left;
    		
    		// 递归地构造左子树，并连接到根节点
    		// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
    		root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
    		// 递归地构造右子树，并连接到根节点
    		// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
    		root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
    		return root;
    	}
    
    	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        
    		int n = preorder.size();
    		// 构造哈希映射，帮助我们快速定位根节点
    		for (int i = 0; i < n; ++i) {
        
    			cout << i << endl;
    			index[inorder[i]] = i;
    		}
    
    		return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    	}
    };
    
    
    int main()
    {
        
    	Solution aa;
    
    	vector<int> preorder = {
         3,9,20,15,7 };
    	vector<int> inorder = {
         9,3,15,20,7 };
    	aa.buildTree(preorder, inorder);
    
    	return 0;
    }

[20210303144404302.png]: /images/20221023/35284c02f80b4f768d72a82bfb0cb859.png