西安建设网站首页,谷歌搜索引擎免费,网站源码文件,信息技术网站建设市场分析题目链接#xff1a;https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/
1. 题目介绍#xff08;07. 重建二叉树#xff09; 输入某二叉树的前序遍历和中序遍历的结果#xff0c;请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的…题目链接https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/
1. 题目介绍07. 重建二叉树 输入某二叉树的前序遍历和中序遍历的结果请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 【测试用例】 示例 1: Input: preorder [3,9,20,15,7], inorder [9,3,15,20,7] Output: [3,9,20,null,null,15,7] 示例 2: Input: preorder [-1], inorder [-1] Output: [-1] 【条件约束】 0 节点个数 5000 2. 题解
2.1 递归 时间复杂度O(n)空间复杂度O(n) 但下列解法仅适用于 “无重复节点值” 的二叉树。 原因在于我们使用了HashMap来存储中序遍历的值和索引也就默认了它的值是唯一的。 前序遍历性质 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。 中序遍历性质 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。 这里的递归用到了分治的思想通过前序遍历我们很容易就可以找到根节点然后我们就可以拿着这个根节点的值去中序遍历中找此时中序遍历根节点的左边就属于当前根的左子树右边就属于当前根的右子树以此类推… /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {// 1. 定义前序遍历索引用于定位当前前序遍历所在的位置int preorderIndex 0;// 2. 创建一个哈希表用于存储中序遍历节点的位置// 后续想要查找元素就可以将时间复杂度降为O(1)HashMapInteger,Integer inorderMap new HashMap();public TreeNode buildTree(int[] preorder, int[] inorder) {// 3. 循环遍历依次将inorder元素添加到哈希表中for (int i 0; i inorder.length; i){inorderMap.put(inorder[i],i);}// 8. 最后返回根节点return arrayToTree(preorder,0,preorder.length-1);}public TreeNode arrayToTree(int[] preorder,int start, int end){// 4. 递归的出口如果左边位置移动到超过右边表示走完了返回空if (start end) return null;// 5. 创建一个TreeNode对象用来保存当前的根节点TreeNode root new TreeNode();root.val preorder[preorderIndex];// 6. 递归找左子树、递归找右子树root.left arrayToTree(preorder,start,inorderMap.get(root.val)-1); root.right arrayToTree(preorder,inorderMap.get(root.val)1,end);// 7. 当前递归结束返回当前节点return root;}
}此外还有很多其它解法例如通过迭代加辅助栈的方法来求解具体内容可参考[2] 重建二叉树力扣官方题解.
3. 可参考
[1] 剑指 Offer 07. 重建二叉树分治算法清晰图解 [2] 重建二叉树力扣官方题解 [3] 【LeetCode】No.105. Construct Binary Tree from Preorder and Inorder Traversal – Java Version 重复
