手机做的兼职网站设计,wordpress深度优化主题,wordpress 缓慢,如何学习做网站题目
105. 从前序与中序遍历序列构造二叉树
分析
这道题是告诉我们一颗二叉树的前序和中序#xff0c;让我们根据前序和中序构造出整颗二叉树。
拿到这道题#xff0c;我们首先要知道前序的中序又怎样的性质#xff1a;
前序#xff1a;【根 左 右】中序#xff1a;…题目
105. 从前序与中序遍历序列构造二叉树
分析
这道题是告诉我们一颗二叉树的前序和中序让我们根据前序和中序构造出整颗二叉树。
拿到这道题我们首先要知道前序的中序又怎样的性质
前序【根 左 右】中序【左 根 右】
根据以上的性质我们可以得到以下的结论
前序遍历的第一个元素一定为数的根节点node的值。因为题目告诉了我们无重复元素所以在中序遍历中找到根节点 node 的索引可以将 中序遍历的数组 划分为 [左子树 | 根节点 | 右子树] 的形式。在中序遍历数组中我们可以知道以 node 为根节点左右子树的节点个数利用这点可以将 前序遍历数组 划分为 [根节点 | 左子树 | 右子树]。通过上面我们可以知道整颗树的树根左子树右子树。下面需要分别构建左子树、右子树还是按照上面的逻辑。
接下来的问题就是需要知道构建左子树和右子树的时候的前序序列和中序序列。
根节点的值为 preorder[0]然后在中序序列中找到这个节点下标为 inorderIndex构建左子树 左子树的 preorder:[1,inorderIndex 1) 左子树的 inorder :[0,inorderIndex ) 构建右子树 右子树的 preorder:[inorderIndex1,preorder.length) 右子树的 inorder :[inorderIndex1,inorder.length) 下面我来举个例子
代码
/*** 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 {public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder.length 0) return null;int rootValue preorder[0];int inorderIndex -1;for(int i 0;i inorder.length;i ) {if(inorder[i] rootValue) {inorderIndex i;break;}}TreeNode rootNode new TreeNode(rootValue);rootNode.left buildTree(Arrays.copyOfRange(preorder,1,inorderIndex1),Arrays.copyOfRange(inorder,0,inorderIndex));rootNode.right buildTree(Arrays.copyOfRange(preorder,inorderIndex1,preorder.length),Arrays.copyOfRange(inorder,inorderIndex1,inorder.length));return rootNode;}
}
