阿里自助建站平台,软件app开发公司哪个好,宁波新亚建设内部网站,郑州网站建设直播课上 一些结论#xff0c;性质 n0,n1,n2指的是子结点的数量#xff0c;n0没有子节点#xff0c;叶子结点 n2*n2n11,若n1为奇数#xff0c;则n为偶数#xff0c;不然#xff0c;则为奇数 满二叉树
没有度为1的结点#xff0c;即每个结点要么没有孩子结点#xff0c;要么…课上 一些结论性质 n0,n1,n2指的是子结点的数量n0没有子节点叶子结点 n2*n2n11,若n1为奇数则n为偶数不然则为奇数 满二叉树
没有度为1的结点即每个结点要么没有孩子结点要么就有两个孩子结点
没有孩子结点的结点一定是叶子结点
回顾
寻找二叉搜索树最近公共祖先
思路是找到从根节点到两个结点的路径由于是一个树所以最开始的路径是一定一样的即在同一颗树上至少具有相同的根节点然后一直往下走走到最后一个分岔口开始分叉即路径中最后一个相同的结点时就是最近公共祖先 始终保持最近的相同结点可以在退出时直接返回最后一个相同的结点即最近公共祖先 找根节点到目标结点的路径是从根节点开始
每次迭代中先入当前结点再更新最后迭代结束加入目标值
寻找二叉树的公共祖先
思路还是找路径然后返回最后一个相同的结点
但由于不是搜索树不满足左子树比根节点小右子树比根节点大的性质所以找路径的方法不同 采用dfs方式找路径如果已经找到了或者是叶子结点尝试继续向下则直接返回
不然就是还没找到先把当前的结点入列然后判断是不是目标值如果是就打上标记并直接返回
不然继续递归向下
遍历两个孩子看flag,如果在左子树里找到了flag就会为1那么在右子树中就不会继续递归不然继续
最后都遍历完后可能找到了也可能没找到找到了就直接返回不操作不然就说明当下的子树里没有应该回溯 二叉树性质复杂度
对于二叉树我们维护一个堆插入和依次获取元素的时间复杂度皆为O(logn)
插入
将元素插入最后一位再进行向上冒泡即如果父节点的值小于被插入的元素父节点下移被插入的元素上移。时间复杂度取决于树的高度h。而完全二叉树的树的高度为[logn1]的上取整所示时间复杂度为O(logn)。
n是插入前的树的结点数插入完后n 选择题 插入排序需要不断移动左序列即遍历到的位置之前是有序的后面是无序的只有到最后才完全有序选择排序是每次选一个最大的交换到序列的相应尾端位置冒泡排序也是这个思路只不过选择排序是选后交换每次只用一次但冒泡排序选和交换同时进行每次至少需要一次
快速排序在有序时最慢为n^2原因 标记一些与……无关的排序 元素的移动次数与关键字的初始排列次序无关的是基数排序
元素的比较次数与初始序列无关是选择排序
算法的时间复杂度与初始序列无关的是选择排序 最坏的情况和最好的情况恰好相反在指定好比较的方向下
如果是从左到右每次都和有序的第一个当前的最小比较那么逆序是最好顺序是最坏
这时插入的判断条件是找到左边为空或比左边大右边为空或比右边小的位置
如果是从右到左每次都和有序的最后一个当前的最大比较那么逆序是最坏顺序是最好
因为逆序时每次接下来的牌都是当前的最小顺序时每次的牌都是当前的最大
