电商网站建设费用,公司宣传网站,企业商城建站,站长工具seo综合查询工具题目
输入某二叉树的前序遍历和中序遍历的结果#xff0c;请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
解题思路
这题较为复杂#xff0c; 首先审题#xff0c;前序遍历规则#xff1a;根左右#xff0c; 中序遍历#x…题目
输入某二叉树的前序遍历和中序遍历的结果请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
解题思路
这题较为复杂 首先审题前序遍历规则根左右 中序遍历 左根右 首先可以知道的是前序遍历的第一个就是根节点然后我们从这个根节点的值找到中序遍历的左子树和右子树 分别在这个前序遍历的根节点值得左边为左子树根节点值得右边为右子树 然后再回到前序遍历 找到根后面相同长度的左子树 和左子树后面相同范围的右子树即可依次类推。然后这题要求返回更节点 首先想到的就是递归一直return到最后的根节点 然后我们这边将中序遍历的每个节点放到map中 主要是为了获取中序遍历的下标 然后我们创建一个递归函数 参数分别是前序遍历根节点所在的Index下标 中序遍历开始位置 中序遍历结束位置 然后大纲就是先创建一个root的TreeNode,用第一个参数前序遍历下标的值 然后将该TreeNode分别指向左子树和右子树 这里就需要用到递归函数了 最后return这个root的TreeNode左子树递归的参数很简单第一个为根下标1即可因为是根左右所以根的下一个下标必为左子树的根第二个开始位置为左子树开始的位置主要注意的是左子树结束的位置为map获取位置的-1然后右子树的递归函数参数最难的就是右子树的根下标位置根的下标位置其实是等于根节点下标 左子树长度 1》 rootIndex (前面左子树结束下标-前面左子树开始下标 1) 1》rootIndex (inorderRootIndex - 1 - left 1) 1 rootIndex inorderRootIndex -left 1, 这就是右子树在前序遍历中开始的位置了 然后右子树的开始位置就是中序遍历RootIndex1的位置 结束位置就是之前的right位置就可以了 具体实现代码如下。
Java解题思路
import java.util.HashMap;
import java.util.Map;
public class BuildTree {public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val x; }}MapInteger, Integer map;int[] preorder;public TreeNode buildTree(int[] preorder, int[] inorder) {this.preorder preorder;map new HashMap();for (int i 0; i inorder.length; i) {map.put(inorder[i], i);}return buildT(0, 0, inorder.length - 1);}private TreeNode buildT(int rootIndex, int left, int right) {if(left right){return null;}int inorderRootIndex map.get(preorder[rootIndex]);TreeNode root new TreeNode(preorder[rootIndex]);root.left buildT(rootIndex 1, left, inorderRootIndex - 1 );root.right buildT(rootIndex inorderRootIndex - left 1 , inorderRootIndex 1, right);return root;}
}
