LeetCode 刷机]105.通过遍历前序和中序序列来构造二叉树 & 106.通过遍历中序和后序序列构建二叉树-105 通过遍历前序和中序序列构建二叉树
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列
思路
根据先序遍历和中序遍历的特点,我们知道先序遍历的第一个节点就是root
,然后在中序遍历中找到root
,那么其左边为左子树,右边为右子树。
利用递归实现的过程,假设先序遍历数组preorder
的区间为[preL,preR]
,中序遍历数组inorder
的区间为[inL,inR]
。那么中间的根节点为preorder[preL]
,利用k
标记找到inorder
中的根节点,那么
左子树节点个数为numLeft = k-inL
.
左子树的先序遍历区间为[preL+1, preL+numLeft]
,中序遍历区间为[inL,k-1]
;
右子树的先序遍历区间为[preL+numLeft+1, preR]
,中序遍历区间为[k+1,inR]
.
这样一直递归下去即可。
PS:图解来自胡凡《算法笔记》P294。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
TreeNode* create(vector<int>& preorder, vector<int>& inorder, int preL,
int preR, int inL, int inR) {
if (preL > preR) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[preL]);
int k;
for (k = 0; k < inorder.size(); k++) {
if (inorder[k] == preorder[preL]) {
break;
}
}
int numLeft = k - inL;
root->left =
create(preorder, inorder, preL + 1, preL + numLeft, inL, k - 1);
root->right =
create(preorder, inorder, preL + numLeft + 1, preR, k + 1, inR);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
return create(preorder, inorder, 0, n - 1, 0, n - 1);
}
};
上一篇: 下载高清壁纸,这些网站就足够了!