在牛客网刷的,还是跟leetcode一样非acm模式,由于急着暑期实习题量不固定,八股算法轮刷
打卡内容偏个人笔记,本人水平一般(代码随想录稀里糊涂刷了一遍),从小白开始分析(甚至会分析语法),尽量一题多解深入探究(一般ac后看看前三个题解发散下思维),希望能对你有帮助
JZ7 重建二叉树
描述
给定节点数为 n 的二叉树的前序遍历和中序遍历结果,请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出如下图所示。
提示:
1.vin.length == pre.length
2.pre 和 vin 均无重复元素
3.vin出现的元素均出现在 pre里
4.只需要返回根结点,系统会自动输出整颗树做答案对比
数据范围:n≤2000,节点的值 −10000≤val≤10000
要求:空间复杂度 O(n),时间复杂度 O(n)
分析
思路数据结构都学过,前序找根节点,中序分割子树
代码刷过再写还是没过,主要不知道写递归还是循环,并且根节点的处理感觉很特殊
于是火速看了算法笔记的二叉树构造部分,记录在我主页算法笔记专栏
上上行提到的问题,还是应该写递归,可以看到同颜色的块是等长的且一个是前序一个是中序,递归参数设置为数组、起始位置和终止位置即可
于是采用前序遍历,做的事是找到inOrder中根节点位置用于后续区间分割
由于有返回值,需要修改代码模板,尽管是前序遍历,在递归函数最后要return root
代码如下:
public TreeNode reConstructBinaryTree(int[] preOrder, int[] vinOrder) {
TreeNode root = build(preOrder, 0, preOrder.length - 1, vinOrder, 0, vinOrder.length - 1);
return root;
}
TreeNode build(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
if (preStart > preEnd) return null;
// Find the index of root node in inorder traversal
int index = 0;
for (int i = inStart; i <= inEnd; i++) {
if (in[i] == pre[preStart]) {
index = i;
break;
}
}
int leftSize = index - inStart;
TreeNode root = new TreeNode(pre[preStart]);
root.left = build(pre, preStart + 1, preStart + leftSize, in, inStart, index - 1);
root.right = build(pre, preStart + leftSize + 1, preEnd, in, index + 1, inEnd);
return root;
}