LeetCode 105. 从前序与中序遍历序列构造二叉树
另一个同源的题目:LeetCode 106. 从中序与后序遍历序列构造二叉树
思路都一样,只是找root
的方式不同。
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size() == 0) return NULL;
int rootVal = preorder[0];
TreeNode* root = new TreeNode(rootVal); //自己构建新树
if(preorder.size() == 1) return root;
auto iter = find(inorder.begin(), inorder.end(), rootVal);
int pivot = iter - inorder.begin(); //找到根结点在中序数组的下标,作为后续分割依据
//切割前序数组,将这层preorder的两个子序列传给下一层
vector<int> leftPreOrder(preorder.begin() + 1, preorder.begin() + pivot + 1);
vector<int> rightPreOrder(preorder.begin() + pivot + 1, preorder.end());
//切割中序数组,将这层inorder的两个子序列传给下一层
vector<int> leftInOrder(inorder.begin(), inorder.begin() + pivot); //左边[)
vector<int> rightInOrder(inorder.begin() + pivot + 1, inorder.end()); //右边(]
root -> left = buildTree(leftPreOrder, leftInOrder);
root -> right = buildTree(rightPreOrder, rightInOrder);
return root;
}
};
原文地址:https://blog.csdn.net/weixin_53024141/article/details/136340300
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!