题目
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。例如,给出
1
2 前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树:
1
2
3
4
5 3
/ \
9 20
/ \
15 7来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
- 这道题在《大话数据结构》上有给出手推的方法,现在需要考虑编程实现。中序(必需)与前序、后序任意一种遍历结果可以唯一确定一棵二叉树。
最重要是确定根节点,我们知道一棵树的前序遍历,其首元素为根节点,而第二个元素(如果有)是它的子节点(不知道左右);而有了根节点(元素不重复即可确定位置),中序遍历中该根节点的前驱(如果有)即为左子节点;找到了左子节点,那么就可以再回到前序遍历中,由于前序遍历中,左子节点的后继节点为右子节点(如果有),那么这样一来就找齐了一个根节点及其左右子节点。- 上一条是错的,血的教训。因为中序遍历根节点的前驱不一定是其左子节点,同样前序遍历的左子节点的后继也不一定是右子节点。重新思考性质:中序遍历永远以根节点为中心把左子树右子树元素一分为二,左侧是左子树元素,右侧是右子树元素。
- 因此,根据以上分析,首先根据前序遍历序列遍历整棵树的根节点(叶节点当成特殊根节点),再递归地建立左右子节点的左右节点。
实现
如果直接对
buildTree
函数掉调用递归,那么建立左右子树需要对应的子树的遍历,对于中序遍历就是以根节点为分界线,两侧分开;那么我们用前序遍历的顺序把元素递归地分开。考虑到在一个序列中找到一个目标之后,需要到另一个序列中寻找此目标位置,如果每次都要遍历寻找浪费了时间,我们需要建立一个哈希表,key为index,value为节点值。此外,需要额外写一个辅助递归函数。
- 函数功能:生成二叉树;
- 结束条件:范围为空:返回
nullptr
; - 递推:构建二叉树 = 构建根节点 + 构建左子树 + 构建右子树
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
lpreorder.assign(preorder.cbegin(), preorder.cend());
linorder.assign(inorder.cbegin(), inorder.cend());
for(auto it=linorder.cbegin(); it!=linorder.cend(); ++it){
inTv2i[*it] = it;
}
cur = lpreorder.cbegin();// cur指的是当前根节点
return buildTreeAux(linorder.cbegin(), linorder.cend());
}
private:
vector<int> lpreorder;
vector<int> linorder;
unordered_map<int, decltype(lpreorder.cbegin())> inTv2i;
decltype(lpreorder.cbegin()) cur;
TreeNode* buildTreeAux(decltype(linorder.cbegin()) lo, decltype(linorder.cbegin()) hi){
if(lo == hi) return nullptr;
auto root_val = *cur;
auto root = new TreeNode(root_val);
++cur;// 将前序遍历下一个节点选为根节点,构建左子树
root->left = buildTreeAux(lo, inTv2i[root_val]);
root->right = buildTreeAux(inTv2i[root_val]+1, hi);
return root;
}
};时间复杂度:
O(N)
,将N个节点全部划分开需要N-1次;空间复杂度O(N)
,存储容器以及哈希表的开销。
拓展
如果用后序遍历和中序遍历构造二叉树呢?
答:逆向遍历后序遍历数组作为当前根节点,构造根节点,右子树和左子树。