文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

類似POJ 2255 Tree Recovery

2. 解題

class Solution { public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {unordered_map<int,int> m;//哈希表for(int i = 0; i < inorder.size(); ++i) {m[inorder[i]] = i;//方便后面查找位置}return build(preorder, inorder,0,preorder.size()-1,0,inorder.size()-1,m);}TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pS, int pE, int iS, int iE, unordered_map<int,int> &m){if(pS > pE)return NULL;TreeNode *root = new TreeNode(preorder[pS]);int leftlen = m[preorder[pS]]-iS;root->left = build(preorder,inorder,pS+1,pS+leftlen,iS,m[preorder[pS]]-1,m);root->right = build(preorder,inorder,pS+1+leftlen,pE,m[preorder[pS]]+1,iE,m);return root;} };

• 別人的循環(huán)解法，很牛，也很難理解

class Solution {//別人寫的，循環(huán)法 public:TreeNode* buildTree(vector<int>& pre, vector<int>& in) {if (pre.empty()) return NULL;stack<TreeNode*> S;TreeNode* root = new TreeNode(pre[0]);S.push(root);for (int i = 1, j = 0; i < pre.size(); i++) { // i-前序序號，j-中序序號TreeNode *back = NULL, *cur = new TreeNode(pre[i]);while (!S.empty() && S.top()->val == in[j]) {back = S.top(), S.pop(), j++;} if (back)back->right = cur;elseS.top()->left = cur;S.push(cur);}return root;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 105. 已知前序中序 求二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。