重庆网站品牌推广,海外设计网站建设,用什么网站做海报,微信建站官网免费注册题目要求
给定两个整数数组 preorder 和 inorder #xff0c;其中 preorder 是二叉树的先序遍历#xff0c; inorder 是同一棵树的中序遍历#xff0c;请构造二叉树并返回其根节点。 提示:
1 preorder.length 3000inorder.length preorder.length-3000 pr…题目要求
给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 提示:
1 preorder.length 3000inorder.length preorder.length-3000 preorder[i], inorder[i] 3000preorder 和 inorder 均 无重复 元素inorder 均出现在 preorderpreorder 保证 为二叉树的前序遍历序列inorder 保证 为二叉树的中序遍历序列
解题思路
一般而言知道一个二叉树的前序遍历和中序遍历就可以确定为唯一二叉树前提是没有重复的子元素在里面。
在前序遍历中我们知道一般是通过根左右的顺序进行遍历所以我们可以在前序遍历中找到根节点和当前根节点的左子树右子树的根节点。
而在中序遍历中根节点的左边是所有左子树的节点根节点的右边是所有右子树的节点依此我们可以推断出左右子树的长度。
根据根节点左右子树的长度作为条件可以使用回溯的方式进行二叉树的构建。
算法流程
递推参数
根节点在前序遍历的索引 root 、子树在中序遍历的左边界 left 、子树在中序遍历的右边界 right 。
终止条件
当 left right 代表已经越过叶节点此时返回 null 。
递推工作
1. 建立根节点 node 节点值为 preorder[root] 。 2. 划分左右子树 查找根节点在中序遍历 inorder 中的索引 i 。、 3. 构建左右子树 开启左右子树递归。
代码解析
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {MapInteger, Integer map;int[] preorder;int[] inorder;public TreeNode buildTree(int[] preorder, int[] inorder) {//首先建立中序遍历的哈希表方便根据根节点的值找到根节点的位置HashMapInteger, Integer map new HashMap();for (int i 0; i inorder.length; i) {map.put(inorder[i], i);}this.map map;this.preorder preorder;this.inorder inorder;return recursion(0,0,inorder.length-1);}public TreeNode recursion(int root, int left, int right) {//终止条件if(left right){return null;}//构建当前根节点TreeNode rootNode new TreeNode(preorder[root]);//当前根节点在中序遍历中的索引位置int rootInOrderindex map.get(preorder[root]);//开始递归构建左子树//左子树的根节点当前根节点在前序遍历的索引1因为 根左右//左子树的左节点在中序遍历中第一个节点必定在左子树中所以左子树的左节点必定是left 0//左子树的右节点中序遍历中右节点必定是当前根节点在中序遍历中的索引位置-1rootNode.left recursion(root1,left,rootInOrderindex-1);//开始递归构建右子树//右子树的根节点在前序遍历中当前根节点加上左子树的长度之后再加一个节点就是有字数的根节点//右子树的左节点在中序遍历中右子树的左节点一般是根节点在中序遍历中的索引1//右子树的右节点中序遍历中右子树的右节点是中序遍历的最后一个节点rootNode.right recursion(root rootInOrderindex - left 1,rootInOrderindex1,right);return rootNode;}
}
