剑指offer 重建二叉树
程序员文章站
2022-06-17 18:26:27
...
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}
和中序遍历序列{4,7,2,1,5,3,8,6}
,则重建二叉树并返回。
与 LeetCode 从前序与中序遍历序列构造二叉树(递归+图解) 一毛一样。
前序遍历:先根节点,后左子树,在右子树
中序遍历:先左子树,后根节点,在右子树
而左子树、右子树的构造又回到了一棵二叉树的构造,递归定义。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//将先序遍历pre[preLeft, preRight]段、中序遍历vin[vinLeft, vinRight]段构造二叉树
TreeNode* myReConstruct(const vector<int> &pre, int preLeft, int preRight, const vector<int> &vin, int vinLeft, int vinRight) {
if (preLeft > preRight) {
//中序遍历为空,返回NULL
return NULL;
} else {
int leftSize = 0;
//计算左子树的大小,先序遍历第一个元素pre[preLeft]就是根,找到中序遍历所在的位置,
while (vin[vinLeft + leftSize] != pre[preLeft]) {
leftSize += 1;
}
//根
TreeNode* root = new TreeNode(pre[preLeft]);
//构建左子树,pre先序遍历构成[preLeft(根),[preLeft + 1, preLeft + leftSize]左子树,[preLeft + leftSize + 1, preRight]右子树]
root->left = myReConstruct(pre, preLeft + 1, preLeft + leftSize, vin, vinLeft, vinLeft + leftSize - 1);
//构建右子树, vin中序遍历构成[[vinLeft, vinLeft + leftSize - 1]左子树,vinLeft + leftSize(根),[vinLeft + leftSize + 1, vinRight]右子树]
root->right = myReConstruct(pre, preLeft + leftSize + 1, preRight, vin, vinLeft + leftSize + 1, vinRight);
return root;
}
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
return myReConstruct(pre, 0, pre.size() - 1, vin, 0, vin.size() - 1);
}
};
题1、LeetCode 从前序与中序遍历序列构造二叉树(递归+图解)
题2、LeetCode 从中序与后序遍历序列构造二叉树(递归+图解)
题3、剑指offer 从尾到头打印链表
推荐阅读
-
《剑指offer》面试题6 重建二叉树
-
剑指offer25:复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),结果返回复制后复杂链表的head。
-
剑指offer31:整数中1出现的次数(从1到n整数中1出现的次数)
-
剑指offer28:找出数组中超过一半的数字。
-
剑指offer27:按字典序打印出该字符串中字符的所有排列
-
C#版剑指Offer-001二维数组中的查找
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
剑指offer13:数组[奇数,偶数],奇数偶数相对位置不变。
-
剑指offer第二天
-
剑指offer JZ31 整数中1出现的次数 Python 解