剑指 Offer(C++版本)系列:剑指 Offer 07 重建二叉树
@[toc]
同步GitHub在此 👉 https://github.com/TeFuirnever/GXL-Skill-Tree
- 剑指 Offer(C++版本)系列:总目录和一些提高效率的说明
- 剑指 Offer(C++版本)系列:剑指 Offer 03 数组中重复的数字
- 剑指 Offer(C++版本)系列:剑指 Offer 04 二维数组中的查找
- 剑指 Offer(C++版本)系列:剑指 Offer 05 替换空格
- 剑指 Offer(C++版本)系列:剑指 Offer 06 从尾到头打印链表
1、题干
重建二叉树 输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3 / \ 9 20 / \ 15 7 限制: 0 <= 节点个数 <= 5000 通过次数158,941提交次数228,915
2、递归法
首先复习一下三种遍历:
- 前序遍历:根节点 | 左子树 | 右子树;
- 中序遍历:左子树 | 根节点 | 右子树;
- 后序遍历:左子树 | 根节点 | 右子树;
然后,重建二叉树,需要知道根节点,左节点,右节点,那么就能重建,这就需要中序遍历,确定根节点所在位置,继而确定左右边界。
最后,当 left > right ,代表已经越过叶节点,此时返回 nullptr ;
算法流程:
- 首先初始化一个哈希表,保存中序遍历值对应的索引;
- 递归重建二叉树;
- 判断递归终止条件:无论是左子树还是右子树,left > right 都终止;
- 前序遍历的最左面结点是根节点的值 rootval ,根节点在中序遍历对应的即为根节点到左边界的长度 k;
- 建立根节点 root : new TreeNode(rootval);
- 构建左右子树: 开启左右子树递归;
前序遍历左边界 | 前序遍历右边界 | 中序遍历左边界 | 中序遍历右边界 | |
---|---|---|---|---|
左子树 | pl + 1 | pl + 1 + len | il | k - 1 |
右子树 | pl + 1 + len | pr | k + 1 | ir |
- 返回值: 根节点 root ,作为上一层递归中根节点的左 / 右子节点;
//面试题07.重建二叉树 //标准做法 /** * 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: unordered_map<int, int> pos; TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int n = preorder.size(); for (int i = 0; i<n; ++i) pos[inorder[i]] = i; return dfs(preorder, inorder, 0, n - 1, 0, n - 1); } TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir) { if (pl>pr) return nullptr; if (il>ir) return nullptr; int rootval = preorder[pl]; int k = pos[rootval]; int len = k - il; auto root = new TreeNode(rootval); root->left = dfs(preorder, inorder, pl + 1, pl + 1 + len, il, k - 1); root->right = dfs(preorder, inorder, pl + 1 + len, pr, k + 1, ir); return root; } };
4、复杂度
/* 时间复杂度:O(n)。对于每个节点都有创建过程以及根据左右子树重建过程。 空间复杂度:O(n)。存储整棵树的开销。 */
——————————————————————————————————————
- 剑指 Offer(C++版本)系列:总目录和一些提高效率的说明
- 剑指 Offer(C++版本)系列:剑指 Offer 03 数组中重复的数字
- 剑指 Offer(C++版本)系列:剑指 Offer 04 二维数组中的查找
- 剑指 Offer(C++版本)系列:剑指 Offer 05 替换空格
- 剑指 Offer(C++版本)系列:剑指 Offer 06 从尾到头打印链表
—————————————————————————————————————
本文由 leetcode、牛客、公众哈哦、知乎共同支持!
https://leetcode-cn.com/u/tefuirnever/
https://blog.nowcoder.net/wsguanxl