appserv做网站教程网站风格定位有哪些

当前位置： 首页 > news >正文

appserv做网站教程,网站风格定位有哪些,wordpress 远程 mysql,html怎么做移动端网站#x1f449; ​​​​​​目录 #x1f448; 1、题一#xff1a;检查两棵树是否相同 1.1 思路分析 1.2 代码 2、题二#xff1a;另一棵树的子树 2.1 思路分析 2.2 代码 3、题三#xff1a;翻转二叉树 3.1 思路分析 3.2 代码 4、题四#xff1a;判断树是否对称 … ​​​​​​目录  1、题一检查两棵树是否相同 1.1 思路分析 1.2 代码 2、题二另一棵树的子树 2.1 思路分析 2.2 代码 3、题三翻转二叉树 3.1 思路分析 3.2 代码 4、题四判断树是否对称 4.1 思路分析 4.2 代码 5、题五判断是否为平衡二叉树 5.1 思路分析 5.1.1 平衡二叉树概念 5.1.2 思路一  O(n^2) 5.1.3 思路一代码  5.1.4 思路二 改善为O(n)【字节跳动面试题】 5.1.5 思路二代码 6、题六将二叉搜索树转化为有序的双向链表 6.1 二叉搜索树的性质 6.2  思路分析 6.3 代码 7、题七二叉树的遍历和构建 7.1  思路分析 ​7.2 代码 1、题一检查两棵树是否相同 . - 力扣LeetCode 1.1 思路分析 两棵树相同需要注意以下几点 两棵树结构相同若结构不相同那两棵树必然是不相同的在结构相同的前提下还需满足节点值相同若结构和节点值都相同那么两棵树相同 额外注意的是若两棵树为空那么也是相同的。 我们可以按照子问题遍历的思想当左子树和右子树中全部节点同时满足以上条件说明两棵树相等。 1.2 代码 时间复杂度Ominm,n class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//如果两棵树都为空那么两棵树相同if(p null q null) {return true;}//如果两棵树的结构不同那这两棵树必然不同if(p ! null q null || p null q ! null) {return false;}//走到这里说明两棵树的结构相同且不为空那判断他们的节点值即可//若节点值不相同则说明两棵树不相同返回falseif(p.val ! q.val) {return false;}//递归遍历//左右两棵子树必须同时满足条件 //才能说明两棵树才相同return isSameTree(p.left,q.left) isSameTree(p.right,q.right);} } 2、题二另一棵树的子树 . - 力扣LeetCode 2.1 思路分析 一棵树的子树 需要满足 这棵子树包括主树的某个节点和这个节点的所有后代节点这棵树自身也可看做自己的子树 了解子树概念后我们可以按照以下思路解决问题 判断子树根节点subRoot和主树根节点root是否相同若相同则调用检查两棵树是否相同的方法题一若相同则为子树若不相同继续遍历判断子树是否和root的左子树相同 若不相同继续遍历判断子树是否和root的右子树相同递归解决问题  2.2 代码 时间复杂度O(m*n) 因为最坏的情况下 每个节点和子树值相同但判断树是否相同时总是最后一个节点不相同 /时间复杂度为O(m*n)因为最坏的情况下每个节点和子树值相同但判断树是否相同时总是最后一个节点不相同 */ class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {//如果递归到空说明没有找到子树返回falseif(root null) {return false;}//判断当前节点的整颗树和子树是否相同即可if(isSameTree(root,subRoot)) {return true;}//如果递归遇见了子树 则一路返回trueif(isSubtree(root.left,subRoot)) return true;if(isSubtree(root.right,subRoot)) return true;//本次递归没有找见子树 返回falsereturn false;}public boolean isSameTree(TreeNode p, TreeNode q) {// 1.先判断结构是否是一样的if (p ! null q null || p null q ! null) {return false;}// 上述if语句 如果没有执行意味着两个引用 同时为空 或者同时不为空if (p null q null) {return true;}// 都不为空 判断值是否一样if (p.val ! q.val) {return false;}// 都不为空且值一样return isSameTree(p.left, q.left) isSameTree(p.right, q.right);} } 3、题三翻转二叉树 . - 力扣LeetCode 3.1 思路分析 这道题的思路很简单就是将每个节点的左右子树进行交换。 我们可以以前序遍历思想遍历所有节点在访问当前树的根节点时将其左右子树进行交换。 3.2 代码 根据解题思想很清晰的分析出时间复杂度为On class Solution {public TreeNode invertTree(TreeNode root) {if(root null) {return null;}//交换左右子树swapNode(root);invertTree(root.left);invertTree(root.right);return root;}public void swapNode(TreeNode root) {TreeNode tmp root.left;root.left root.right;root.right tmp;} } 4、题四判断树是否对称 . - 力扣LeetCode 4.1 思路分析 要判断这颗树是对称的 就要判断根节点的左子树和右子树是对称的 要判断根节点的左子树和右子树是对称的 需要左右子树的结构相同在结构相同前提下节点的值要相同如果结构相同了值也相同了那么要递归去判断左子树的左树和右子树的右树是否轴对称是否结构相同、值相同以及左子树的右树和右子树的左树是否轴对称是否结构相同、值相同。均满足我们只能递归来一个节点一个节点的去遍历去判断去比较 4.2 代码 class Solution {public boolean isSymmetric(TreeNode root) {if(root null) {return true;}return isSymmetricChild(root.left,root.right);}public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {//空树对称if(leftTree null rightTree null) {return true;}//结构不相同 必定不对称if(leftTree ! null rightTree null || leftTree null rightTree ! null) {return false;}//节点值不相同 必定不对称if(leftTree.val ! rightTree.val) {return false;}//左子树的左树和右子树的右树 //左子树的右树和右子树的左树//都要对称return isSymmetricChild(leftTree.left,rightTree.right) isSymmetricChild(leftTree.right,rightTree.left);} } 5、题五判断是否为平衡二叉树 . - 力扣LeetCode 5.1 思路分析 5.1.1 平衡二叉树概念 如果一棵树是平衡二叉树那么满足 树中所有节点的左右子树高度差1 也就是说每一棵子树都是平衡二叉树 根据平衡二叉树的概念我们有以下两种思路解决问题。 5.1.2 思路一  O(n^2) 递归遍历所有节点求出每个节点的左右子树高度差若出现2的情况立即返回false当前节点的左树上的节点和右树上的节点全部满足高度差1 时说明为平衡二叉树该思路时间复杂度为On^2求根节点高度的方法时间复杂度本来就为On而要求得所有节点的高度时间复杂度就为On^2 5.1.3 思路一代码  class Solution {public boolean isBalanced(TreeNode root) {//空树 平衡if(root null) {return true;}//当前节点左子树高度int h1 getHeight(root.left);//当前节点右子树高度int h2 getHeight(root.right);int h Math.abs(h1-h2);//高度差//不平衡if(h 2) return false;//左子树和右子树同时平衡 说明整棵树平衡return isBalanced(root.left) isBalanced(root.right);}public int getHeight(TreeNode root) {if (root null) {return 0;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);//树的高度为 左子树高度和右子树高度的最大值节点自身的1个高度return leftHeight rightHeight? leftHeight 1: rightHeight 1;} } 5.1.4 思路二 改善为O(n)【字节跳动面试题】 思路一虽然能解决问题但时间复杂度达到了O(n^2)并且产生了很多次重复的计算,例如圈中节点的高度在计算它祖先的高度时就被计算了多次产生了很多重复的计算。 如果要将时间复杂度改善为O(n)该如何完成呢 O(n)思路分析 我们可以只求根节点的高度在求节点高度时我们使用递归遍历思想返回的是左右子树高度的最大值1左右子树最大高度节点自身1个高度而我们可以将求高度的方法进行改善在递归过程中一旦发现左右子树高度差绝对值2时说明不平衡立即返回负数标记其他标记也可如果高度差绝对值1时说明平衡返回正常的高度值即可。如若发现返回的是负数立即一路返回负数。最终判断方法的返回值即可若为负数则说明该树不平衡若为正数高度值说明该树平衡。 5.1.5 思路二代码 class Solution {/时间复杂度On*/public boolean isBalanced(TreeNode root) {if(root null) {return true;}//负数说明该树不平衡return getHeight(root) 0;}public int getHeight(TreeNode root) {if (root null) {return 0;}int leftHeight getHeight(root.left);//如若发现返回的是负数则说明该树一定不平衡一路返回负数if(leftHeight 0) {return -1;}//如若发现返回的是负数则说明该树一定不平衡一路返回负数int rightHeight getHeight(root.right);if(rightHeight 0) {return -1;}//如果绝对值1 说明当前树平衡返回高度值if(Math.abs(leftHeight - rightHeight) 1) {return Math.max(leftHeight , rightHeight) 1;}else {//否则返回负数return -1;}} } 6、题六将二叉搜索树转化为有序的双向链表 二叉搜索树与双向链表_牛客题霸_牛客网 6.1 二叉搜索树的性质 二叉搜索树又称二叉排序树、二叉查找树具有以下性质 若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值二叉搜索树可以为空树以中序遍历来遍历一棵二叉搜索树那么得到的序列就是一个有序的升序序列。 6.2  思路分析 以中序遍历递归这棵二叉搜索树将得到的根节点依次连接修改其左右指针得到的就是排好序的双向链表。 借助中序遍历思想递归遍历各个节点修改指向将每个节点的left域当做双向链表中的prev域将right域当做next域借助一个成员变量prev存储上一个节点的地址完成各节点指向的修改和连接 6.3 代码 时间复杂度On public class Solution {//定义一个成员变量 存储上一个节点的地址TreeNode prev;//初始值为nullpublic void ConvertNode(TreeNode pRootOfTree) {if(pRootOfTree null) return;//中序遍历思想递归ConvertNode(pRootOfTree.left);//修改前驱将当前节点的left域更改为前一个节点的地址pRootOfTree.left prev;if (prev ! null) {//当prev不为空时修改后继//将其right域修改为当前节点的地址prev本就是当前节点的前驱prev.right pRootOfTree;}//更新prevprev pRootOfTree;ConvertNode(pRootOfTree.right);}public TreeNode Convert(TreeNode pRootOfTree) {if (pRootOfTree null) {return null;}ConvertNode(pRootOfTree);TreeNode head pRootOfTree;//找头结点//转换成双向链表后链表的头结点就在pRootOfTree的左边//头结点的left前驱为nullwhile(head.left ! null) {head head.left;}return head;} } 7、题七二叉树的遍历和构建 二叉树遍历_牛客题霸_牛客网 7.1  思路分析 我们知道如果仅仅根据一个遍历方式的结果是无法构建出一棵二叉树的必须有两个遍历方式且必须包含中序遍历。 而这道题是不同的因为题目给出的遍历结果包含了空树所以仅仅利用一个遍历方式我们就可以构建出二叉树。 只要构建出这棵二叉树我们再使用中序遍历递归打印节点值就可以了。 难点在如何使用代码根据前序遍历来构建二叉树 思路如下 题目仅仅给出了main方法意味着我们要自己创建节点创建的节点类要满足树中节点的要求包含val域char类型、left域、right域同时要给出构造方法创建二叉树肯定是要遍历前序遍历结果的字符串这里以静态i成员遍历字符串给出的是前序遍历结果所以要以前序遍历的思想递归来创建树如果遍历到的字符不是#说明不是空树实例出该值的节点i此时仅仅实例节点各节点间并没有连接创建左子树创建右子树如果遇到的字符是#说明遇到是空树i返回空节点递归回退上一个节点的left或者right接收如果节点的左子树或者右子树创建完成递归回退上一个节点的left或者right接收如果节点的左子树和右子树都创建完成本次递归函数结束递归回退上一个节点的left或者right接收也就是说我们在递归回退的过程中完成节点之间的连接最后一步以中序遍历形式来访问根节点并打印 注意这里因为题目条件限制只能使用静态成员i来遍历字符串。但是对于我们实际的应用不建议使用静态成员因为当创建多个对象时他们都会使用并改变i的值而创建二叉树时必须从0下标处遍历字符串 7.2 代码 import java.util.Scanner;//节点 class TreeNode {TreeNode left;TreeNode right;char val;public TreeNode(char val) {this.val val;} } // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 case//防止有多组测试用例每次使用时i要置0Main.i 0;String str in.nextLine();TreeNode root creatTree(str);InOrder(root);}}public static int i;public static TreeNode creatTree(String str) {TreeNode node null;if (str.charAt(i) ! #) {//不是空树就实例化该值的节点node new TreeNode(str.charAt(i));i;//在递归回退的过程中完成节点之间的连接node.left creatTree(str);node.right creatTree(str);} else {//是空树ii;}return node;}//中序遍历打印根节点public static void InOrder(TreeNode root) {if (root null) {return;}InOrder(root.left);System.out.print(root.val );InOrder(root.right);} }