105. Construct Binary Tree from Preorder and Inorder Traversal

2019-11-10 21:44:58

字体：大中小

来源：转载

供稿：网友

必须要学习的代码，很骚！

/** * 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 {public: TreeNode* create(vector<int>& PReorder, vector<int>& inorder, int ps, int pe, int is, int ie){ if(ps > pe) return NULL; TreeNode* node = new TreeNode(preorder[ps]); int pos; for(int i = is; i <= ie; ++ i){ if(inorder[i] == node -> val){ pos = i; break; } } node -> left = create(preorder, inorder, ps + 1, ps + pos - is, is, pos - 1); node -> right = create(preorder, inorder, ps + pos - is + 1, pe, pos + 1, ie); return node; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { return create(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1); }

上一篇：MFC线程间通信

下一篇：100道动态规划——27 POJ 1185 炮兵阵地状态压缩，预处理，滚动数组