剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
根据前序或者后序序列+中序序列构建二叉树是一道非常非常非常经典的题目, 除了剑指offr 在leetcode主站也有两道完全相同的题:
106.Construct Binary Tree from Inorder and Postorder Traversal
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { private: unordered_map<int,int> dp; public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { // 存储中序数组中每个元素对应的位置 for(int i=0;ii){ dp[inorder[i]]=i; } int mid=0; return make_tree(0,inorder.size()-1,mid,preorder); } TreeNode* make_tree(int left,int right,int &mid,vector<int>& preorder){ if(left>right) return NULL; int num=preorder[mid]; int divide=dp[num]; // 构建当前节点 TreeNode* root= new TreeNode(num); // 下一个根节点 mid++; // 先构建左子树 root->left=make_tree(left,divide-1,mid,preorder); // 然后构建右子树 root->right=make_tree(divide+1,right,mid,preorder); return root; } };