【免费】剑指offer剑指offer资源-CSDN文库

需积分: 0 18 浏览量 2024-01-25 08:49:17 上传评论收藏 226KB DOCX 举报

资源推荐

资源详情

资源评论

快速排序: 快排的常数项很低, 因为每一步partition过程操作数量很低, 即它的常数项很

低, 所以快速排序在工程上是最被经常使用的排序算法.

空间复杂度: 在整个函数中, 整个函数没返回前所需要的空间叫空间复杂度, 某一部分子过程

的变量空间在整个函数返回前已经释放了, 就不用算作整个的空间复杂度了.

二叉树题目的套路: (

这些题目有着统一的名字

:

叫做树形

DP) ---> 树形DP都是利用后

序遍历?

一系列二叉树的问题 (求整棵树的******…), 统一的处理逻辑就是: 假设以每一个节点为头

的这棵树, 它的最大搜索二叉子树是什么

如果我们求出来了以每一个节点为头的最大二叉搜索子树, 答案一定在其中.

相当于, 一开始进入第一层递归时就已经拿到了下一层的节点的黑盒（看成已知数）, 然后根

据这个黑盒进行拆数据并整理成新数据, 并把新数据整理成本层节点的黑盒, 最后返回至最外

层中.

//这种动态规划比在数组中、和矩阵中做动态规划更为方便: 因为遍历顺序就决定了先遍历子

树, 再遍历父树, 所以它的计算顺序都高度固定了.

//判断完全二叉树:

//Deque是一个双端链表, 双向队列。正常的队列是从头进, 从尾出; 而Deque是头尾都能进

出。Deque和Queue是应用中的叫法, 底层都可以用双端链表来实现. 同理, 优先级队列和堆

也是一个东西. 用数组可以实现一个堆, 用二叉树也可以实现堆（code很难写, 需要处理的边

界特别多）. 但二叉树实现堆的好处是不会浪费空间, 没有扩容代价（但数组实现堆就有

了）. 此问题在《程序员代码面试指南》中有涉及到.

public class Solution {

public static boolean isCBT(Node head) {

if (head == null) {

return true;

}

Queue<Node> queue = new LinkedList<Node>();

boolean leaf = false;

Node l = null;

Node r = null;

queue.offer(head);

while (!queue.isEmpty()) {

head = queue.poll();

l = head.left;

r = head.right;

if ((leaf && (l != null || r != null)) || (l == null && r != null)) { //这一个if

语句，两种判断标准就都包含了进去。合二为一了

return false;

}

if (l != null) {

剩余62页未读，继续阅读

内容反馈

qq_40849626

粉丝: 6
资源: 15

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip