数据结构与算法——左程云05
【前言】：
后续有时间会把文中的图片整理好，将纸质笔记中的图做成JPG。
【1】：链表遗留
【单链表相交】：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-K0WslDXs-1663993923868)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220819223715371.png)]
//这道题本身和节点上的值是没有关系的；
//两个链表中有某一个节点的内存地址是同一个，那我们就说这两个链表相交。
【理解相交】：
【判断函数】：
一个链表如果有环，那么请返回第一个入环的节点 ， 如果无环，则返回NULL；
（入参）——该链表的头节点；
【简单的哈希表方法】：
【不存在的结构】：
如果一个链表有环，那么它一定会掉入到自己的环中出不来，它一定会掉入到自己的环里出不来，也不可能走到NULL，每一个节点都只能有一条往外指的next指针；
【总结】：
找一个变量一直往下走 ， 如果它走到空节点了 ， 这个链表它肯定是没有环的，如果它走不到空节点，你又因为把沿途的节点都放到了哈希表里去 ， 你每到一个节点都去查——当前的节点在不在哈希表里，如果有环，你一定会遇到——这个重复发现的时刻。当你发现下一个节点是哈希表中已经有的节点，那么该结点一定是第一个入环的节点。
【不用哈希表Find第一个入环的节点】：
//如果无环，肯定会走到NULL；
//如果有环，一定会陷入循环；
【 无环单链表情况讨论 】：
【求无环单链表相交节点】：
【有环链表情况讨论】：
【2】：二叉树
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PJaDCSbF-1663993923869)(/Users/yuguangyao/Library/Application Support/typora-user-images/image-20220820203038462.png)]
【叶子节点】：
左右孩子都为null 的节点；
【递归序】：
public static void preOrderRecur(Node head) {
if (head == null) {
return;
}
System.out.print(head.value ); //【第一次】
// 1
preOrderRecur(head.left); //左侧去递归遍历 ～
System.out.print(head.value ); //【第二次】
// 2
preOrderRecur(head.right); //右侧去递归遍历 ～
System.out.print(head.value ); //【第三次】
}
//递归方法去完成二叉树的遍历 ， 每一个节点都能回个3次（ 每一个节点中的数字，都能在篮框中找到3次 ）；
//虽然某一次的时候可能什么也没干 ， 但是， 它是可以回到的。
【三序遍历】：
在递归序的基础上，可以加工出三种顺序的遍历——先序、中序、后序。
【先序遍历】：
对于所有子树来说——先打印头节点，再打印左子树上所有的节点 ， 再打印右子树上所有的节点；
//只在第一次的时候打印 ， 二、三次的时候 ， 什么也不干～ ～ ～ ！ ！ ！
【中序遍历】：
利用递归序，第二次来到该节点的时候才打印 ， 不是第二次来到该节点的什么也不做。
【后序遍历】：
递归序中第三次的打印——后序。
【总结】：
先序、中序、后序 都可以由 《递归序》加工过来（只是选择打印的时机不同。）
【非递归频率】：
非递归行为在面试场上经常出现 ， 看你有没有理解～～～！！！
【非递归实现三序】：
//任何递归函数都可以改成非递归函数——这是一定的！！！
【非递归先序】：
【非递归后序】：
【非递归中序】：
【左边界】：
所有的树都是可以被《左边界》给分解掉的 ～
【树打印福利函数】：
【二叉树面试】:
二叉树的Coding难度大于链表，单很少考二叉树Coding的难度 ， 一般都是算法居多。
【二叉树的深度优先遍历】：
对于二叉树来说，深度优先遍历就是==〉先序遍历。
【二叉树的宽度优先遍历】：
【求一颗二叉树的最大宽度】：
//你要能知道当前的节点在第几层 ， 你还得统计这一层有多少个节点～～～
【得有一种机制】：
知道在遍历的过程中 ， 哪一层的范围是多少。
-
代码才是核心（ 此题无法图解 ）
-
《@@71_18》
【新手研究方法】：
用纸画图 ， 一点儿一点儿扣 ， 看上去似乎很笨 ， 但是这至少能保证你能看懂；
【求一颗二叉树的最大宽度（不用哈希表）】：
Node curend //当前层最后一个节点；( 你现在弹出的节点所在层中，这一层的最后一个节点 )
Node nextend. //下一层最后一个节点；（ 当前所在层的下一层 ）
int curlevel //当前层发现的节点数；
int max //结算时的节点数————当前层的节点总数；