行业网站建设方案,有专门做电商网站的CMS吗,深圳瑞仕建设公司,广州深圳题目
105. 从前序与中序遍历序列构造二叉树 - 力扣#xff08;LeetCode#xff09; 思路
首先思考#xff0c;根节点应该做什么。
肯定要想办法确定根节点的值#xff0c;把根节点做出来#xff0c;然后递归构造左右子树即可。
我们先来回顾一下#xff0c;前序遍历和…题目
105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode 思路
首先思考根节点应该做什么。
肯定要想办法确定根节点的值把根节点做出来然后递归构造左右子树即可。
我们先来回顾一下前序遍历和中序遍历的结果有什么特点
void traverse(TreeNode root) {// 前序遍历preorder.add(root.val);traverse(root.left);traverse(root.right);
}void traverse(TreeNode root) {traverse(root.left);// 中序遍历inorder.add(root.val);traverse(root.right);
}
关键在于如何通过根节点的值将 preorder 和 inorder 数组划分成两半构造根节点的左右子树
换句话说对于以下代码中的 ? 部分应该填入什么
/* 主函数 */
public TreeNode buildTree(int[] preorder, int[] inorder) {// 根据函数定义用 preorder 和 inorder 构造二叉树return build(preorder, 0, preorder.length - 1,inorder, 0, inorder.length - 1);
}/* build 函数的定义若前序遍历数组为 preorder[preStart..preEnd]中序遍历数组为 inorder[inStart..inEnd]构造二叉树返回该二叉树的根节点
*/
TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {// root 节点对应的值就是前序遍历数组的第一个元素int rootVal preorder[preStart];// rootVal 在中序遍历数组中的索引int index 0;for (int i inStart; i inEnd; i) {if (inorder[i] rootVal) {index i;break;}}TreeNode root new TreeNode(rootVal);// 递归构造左右子树root.left build(preorder, ?, ?,inorder, ?, ?);root.right build(preorder, ?, ?,inorder, ?, ?);return root;
}
对于代码中的 rootVal 和 index 变量就是下图这种情况 另外也有读者注意到通过 for 循环遍历的方式去确定 index 效率不算高可以进一步优化。
因为题目说二叉树节点的值不存在重复所以可以使用一个 HashMap 存储元素到索引的映射这样就可以直接通过 HashMap 查到 rootVal 对应的 index
// 存储 inorder 中值到索引的映射
HashMapInteger, Integer valToIndex new HashMap();public TreeNode buildTree(int[] preorder, int[] inorder) {for (int i 0; i inorder.length; i) {valToIndex.put(inorder[i], i);}return build(preorder, 0, preorder.length - 1,inorder, 0, inorder.length - 1);
}TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {int rootVal preorder[preStart];// 避免 for 循环寻找 rootValint index valToIndex.get(rootVal);// ...
}
现在我们来看图做填空题下面这几个问号处应该填什么
root.left build(preorder, ?, ?,inorder, ?, ?);root.right build(preorder, ?, ?,inorder, ?, ?);
对于左右子树对应的 inorder 数组的起始索引和终止索引比较容易确定 root.left build(preorder, ?, ?,inorder, inStart, index - 1);root.right build(preorder, ?, ?,inorder, index 1, inEnd);
对于 preorder 数组呢如何确定左右数组对应的起始索引和终止索引
这个可以通过左子树的节点数推导出来假设左子树的节点数为 leftSize那么 preorder 数组上的索引情况是这样的 看着这个图就可以把 preorder 对应的索引写进去了
int leftSize index - inStart;root.left build(preorder, preStart 1, preStart leftSize,inorder, inStart, index - 1);root.right build(preorder, preStart leftSize 1, preEnd,inorder, index 1, inEnd);
至此整个算法思路就完成了我们再补一补 base case 即可写出解法代码
TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {if (preStart preEnd) {return null;}// root 节点对应的值就是前序遍历数组的第一个元素int rootVal preorder[preStart];// rootVal 在中序遍历数组中的索引int index valToIndex.get(rootVal);int leftSize index - inStart;// 先构造出当前根节点TreeNode root new TreeNode(rootVal);// 递归构造左右子树root.left build(preorder, preStart 1, preStart leftSize,inorder, inStart, index - 1);root.right build(preorder, preStart leftSize 1, preEnd,inorder, index 1, inEnd);return root;
}
我们的主函数只要调用 build 函数即可你看着函数这么多参数解法这么多代码似乎比我们上面讲的那道题难很多让人望而生畏实际上呢这些参数无非就是控制数组起止位置的画个图就能解决了。 代码
class Solution {// 存储 inorder 中值到索引的映射HashMapInteger, Integer valToIndex new HashMap();public TreeNode buildTree(int[] preorder, int[] inorder) {for (int i 0; i inorder.length; i) {valToIndex.put(inorder[i], i);}return build(preorder, 0, preorder.length - 1,inorder, 0, inorder.length - 1);}TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {if (preStart preEnd) {return null;}// root 节点对应的值就是前序遍历数组的第一个元素int rootVal preorder[preStart];// rootVal 在中序遍历数组中的索引int index valToIndex.get(rootVal);int leftSize index - inStart;// 先构造出当前根节点 TreeNode root new TreeNode(rootVal);// 递归构造左右子树root.left build(preorder, preStart 1, preStart leftSize,inorder, inStart, index - 1);root.right build(preorder, preStart leftSize 1, preEnd,inorder, index 1, inEnd);return root;}
}
