题解 | #重建二叉树#
重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param preOrder int整型vector * @param vinOrder int整型vector * @return TreeNode类 */ TreeNode* reConstructBinaryTree(vector<int> preOrder, vector<int> vinOrder) { // write code here if(preOrder.size()==0 || vinOrder.size()==0){ return NULL; } auto* root = new TreeNode(preOrder[0]); for(int i=0;i<preOrder.size();i++){ if(preOrder[0] == vinOrder[i]){ vector<int> leftpre(preOrder.begin() + 1, preOrder.begin()+1+i); vector<int> leftvin(vinOrder.begin(), vinOrder.begin()+i); root->left = reConstructBinaryTree(leftpre, leftvin); vector<int> rightpre(preOrder.begin() + 1+i, preOrder.end()); vector<int> rightvin(vinOrder.begin()+i+1, vinOrder.end()); root->right = reConstructBinaryTree(rightpre, rightvin); break; } } return root; } };
要用过前序和中序查找结果来重建二叉树,可以将任务分为多个子任务,使用递归来实现。具体而言,利用前序排序的第一个元素为根节点,找到树的根节点,然后在中序排序中查找根节点,再根据中序排序得到下一层的左子树和右子树,递归实现根节点寻找,最后回溯时返回整个树。