莱芜市城乡建设局网站首页,如何把网站建设成营销型网站,哪个网站可以找人做橱柜,做网站公司哪里好1. 定义 二叉树是一种树形数据结构#xff0c;由节点组成#xff0c;每个节点最多有两个子节点#xff0c;分别为左子节点和右子节点。二叉树具有以下性质#xff1a; 每个节点最多有两个子节点#xff0c;称为左子节点和右子节点。 左子节点和右子节点可以为空#xff0…1. 定义 二叉树是一种树形数据结构由节点组成每个节点最多有两个子节点分别为左子节点和右子节点。二叉树具有以下性质 每个节点最多有两个子节点称为左子节点和右子节点。 左子节点和右子节点可以为空即一个节点没有子节点或只有一个子节点。二叉树的子树也是二叉树即每个子节点都可以看作是根节点构成一个新的二叉树。二叉树可以是空树即不包含任何节点的情况。二叉树的节点之间不存在环即不能通过任意路径从一个节点回到自身。 2. 遍历 二叉树的遍历主要有三种方式前序遍历、中序遍历和后序遍历。 前序遍历是根据【根-左-右】的顺序进行遍历即首先访问根节点然后访问左子树最后访问右子树。中序遍历是根据【左-根-右】的顺序进行遍历即首先访问左子树然后访问根节点最后访问右子树。后序遍历是根据【左-右-根】的顺序进行遍历首先访问左子树然后访问右子树最后访问根节点。 3. 节点结构定义
构建二叉树首先要构造二叉树的节点以下是二叉树节点的定义
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;}
}在上述代码中我们定义了一个名为TreeNode的类包含了节点的值val、左子节点left、右子节点right三个成员变量。同时我们提供了三个构造方法分别用于创建空节点、只含值的节点和含值、左右子节点的节点。
4. 通过遍历结果生成二叉树
前提无重复值
1. 已知前中序遍历生成二叉树 力扣105
常用递归写法 将问题拆分为一个个子问题即将每个二叉树结点当作一个子问题来求解。
public TreeNode buildTree(int[] preorder, int[] inorder) {int n preorder.length;if(n 0){return null;}int leftSize indexOf(inorder,preorder[0]);int[] pre1 Arrays.copyOfRange(preorder,1,1leftSize);int[] pre2 Arrays.copyOfRange(preorder,1leftSize,n);int[] in1 Arrays.copyOfRange(inorder,0,leftSize);int[] in2 Arrays.copyOfRange(inorder,leftSize1,n);TreeNode left buildTree(pre1,in1);TreeNode right buildTree(pre2,in2);return new TreeNode(preorder[0],left,right);
}
public int indexOf(int[] inorder,int x){for(int i 0;i inorder.length;i){if(inorder[i] x){return i;}}return -1;
}时间复杂度O(n^2)空间复杂度 O(n^2) 2. 在上述方法需要遍历整个集合求出根结点的下标时间复杂度为O(n)可以使用哈希表来进一步简化这一过程
public TreeNode buildTree(int[] preorder,int[] inorder){int n preorder.length;MapInteger,Integer index new HashMapInteger,Integer();for(int i 0;i n;i){index.put(inorder[i],i);}return dfs(preorder,0,n,inorder,0,n,index);}public TreeNode dfs(int[] preorder,int preL,int preR,int[] inorder,int inL,int inR,MapInteger,Integer index){if(preL preR){return null;}int leftSize index.get(preorder[preL]) - inL;TreeNode left dfs(preorder,preL 1,preL 1 leftSize,inorder,inL,inLleftSize,index);TreeNode right dfs(preorder,preL 1 leftSize,preR,inorder,inLleftSize 1,inR,index);return new TreeNode(preorder[preL],left,right);} 时间复杂度O(n)空间复杂度O(n)
2. 已知中后序遍历生成二叉树 力扣106
常用递归写法 首先要确定左子树的长度然后根据中后序遍历的特点进行节点划分。
public TreeNode buildTree(int[] inorder, int[] postorder) {int n inorder.length;if(n 0){return null;}int leftSize indexOf(inorder,postorder[n - 1]);int[] inL Arrays.copyOfRange(inorder,0,leftSize);int[] inR Arrays.copyOfRange(inorder,leftSize 1,n);int[] postL Arrays.copyOfRange(postorder,0,leftSize);int[] postR Arrays.copyOfRange(postorder,leftSize,n - 1);TreeNode left buildTree(inL,postL);TreeNode right buildTree(inR,postR);return new TreeNode(postorder[n-1],left,right);}public int indexOf(int[] arr,int x){int n arr.length;for(int i 0;i n;i){if(arr[i] x){return i;}}return -1;}时间复杂度O(n^2)空间复杂度 O(n^2) 3. 使用哈希表来进一步简化
public TreeNode buildTree(int[] inorder, int[] postorder) {int n inorder.length;HashMapInteger,Integer index new HashMapInteger,Integer();for(int i 0;i n;i){index.put(inorder[i],i);}return dfs(inorder,0,n-1,postorder,0,n-1,index);}public TreeNode dfs(int[] inorder,int inL,int inR,int[] postorder,int postL,int postR,HashMapInteger,Integer index){if(inL inR){return null;}if(inL inR){return new TreeNode(inorder[inL]);}int leftSize index.get(postorder[postR]) - inL;TreeNode left dfs(inorder,inL,inL leftSize - 1,postorder,postL,postL leftSize - 1,index);TreeNode right dfs(inorder,inL leftSize 1,inR,postorder,postL leftSize,postR - 1,index);return new TreeNode(postorder[postR],left,right);}时间复杂度O(n)空间复杂度O(n)
2. 已知前后序遍历生成二叉树 力扣889
常用递归写法
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {int n preorder.length;if(n 0){return null;}if(n 1){return new TreeNode(preorder[0]);}int leftSize indexOf(postorder,preorder[1]) 1;int[] preL Arrays.copyOfRange(preorder,1,leftSize 1);int[] preR Arrays.copyOfRange(preorder,leftSize 1,n);int[] postL Arrays.copyOfRange(postorder,0,leftSize);int[] postR Arrays.copyOfRange(postorder,leftSize,n-1);TreeNode left constructFromPrePost(preL,postL);TreeNode right constructFromPrePost(preR,postR);return new TreeNode(preorder[0],left,right);}public int indexOf(int[] arr,int x){int n arr.length;for(int i 0; i n;i){if(arr[i] x){return i;}}return -1;}时间复杂度O(n^2)空间复杂度 O(n^2) 2. 使用哈希表来进一步简化
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {int n preorder.length;HashMapInteger,Integer index new HashMapInteger,Integer();for(int i 0;i n;i){index.put(postorder[i],i);}return dfs(preorder,0,n-1,postorder,0,n-1,index);}public TreeNode dfs(int[] preorder,int preL,int preR,int[] postorder,int postL,int postR,HashMapInteger,Integer index){if(preL preR)return null;if(preL preR)return new TreeNode(preorder[preL]);int leftSize index.get(preorder[preL 1]) - postL 1;TreeNode left dfs(preorder,preL 1,preL leftSize,postorder,postL,postL leftSize - 1,index);TreeNode right dfs(preorder,preL leftSize 1,preR,postorder,postL leftSize,postR - 1,index);return new TreeNode(preorder[preL],left,right);}时间复杂度O(n)空间复杂度O(n)
5. 总结
通过前中、前后、中后遍历结果生成二叉树关键点在于确定左子树和右子树的边缘范围。
