提示：本节来说二叉树的Morris遍历，面试的高超优化技能！
此前学的关于二叉树的概念，先序遍历，中序遍历，后续遍历（这仨统称DFS遍历）和按层的方式遍历（俗称BFS遍历）重要的基础知识：
【1】二叉树，二叉树的归先序遍历，中序遍历，后序遍历，递归和非递归实现
【2】二叉树的宽度优先遍历BFS：按层的遍历方式，请你用队列实现DFS，或者请你用栈实现BFS
【3】求二叉树中，包含的最大二叉搜索子树的头节点是谁，它包含的节点数量是多少
这仨文章，都是重要的基础知识，笔试的时候可以用
面试的时候，除了上面仨，咱们还可以说一下Morris遍历的优化技能
Morris遍历的基础知识，有了这个知识，你才能看懂今天的题目解法
【4】Morris遍历：与二叉树的递归遍历（DFS/BFS）不同，优化空间复杂度为o(1)
【5】二叉树的Morris遍历：先序遍历和中序遍历
【6】Morris遍历判断二叉树是否为搜索二叉树
文章目录
- 求二叉树的最小高度
- @[TOC](文章目录)
- 题目
- 一、审题
- 笔试AC解：树形DP：二叉树的递归套路
- 面试精华解：Morris遍历优化
- Morris遍历代码
- 利用Morris遍历求最小高度
- 总结
求二叉树的最小高度
最小高度是真二叉树的叶节点到头结点的高度中，最小高度。
1个节点算高度1
一、审题
示例：
下图，最小高度2
笔试AC解：树形DP：二叉树的递归套路
递归套路嘛，那就得左右收集信息
x极其以下的树，最小的高度h多少呢？下图x=5
下面的最小高度，是3这个叶节点到x的高度
跟求树的高度不一样，x=5这个树，整体高度是最大高度height=4；
所以咱们收集信息就收集最小高度h
定义信息为：
//复习树形DP
public static class Info{
public int h;
public Info(int t){
h = t;//收集最小高度信息
}
}
手撕递归套路：
//递归f
public static Info f(Node x){
if (x == null) return new Info(0);//叶节点null高度就是0，叶节点高度是1
//左右收集信息
Info left = f(x.left);
Info right = f(x.right);
//整理信息
int h = Math.min(left.h, right.h) + 1;
return new Info(h);
}
//调用
public static int minHeightReview(Node head){
if (head == null) return 0;
Info info = f(head);
return info.h;
}
相比于其他的二叉树的题目，这已经是非常简单了
测试
public static void test(){
Node head = createTree();
Node head2 = createTree();
int h = minHight(head);
System.out.println(h);
System.out.println();
System.out.println(minHeightReview(head2));
}
//如果非要高逼格的话，那就是面试，Morris算法
public static void main(String[] args) {
test();
}
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int v){
value = v;
}
}
//造树，长啥样呢：
// 1
// 2 3
// 4 5 6 7
// 8
public static Node createTree(){
Node head = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
Node n7 = new Node(7);
Node n8 = new Node(8);
head.left = n2;
head.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;
n4.left = n8;
return head;
}
问题不大
3 3
面试精华解：Morris遍历优化 Morris遍历代码
Morris遍历的流程：
（0）cur默认最开始指向head，mR默认为null【即cur左树的最右节点】，判断cur是否有左树？
（1）cur如果没有左树，直接去右树cur=cur.right（当然没有右树那停止Morris遍历）
（2）cur如果有左树，先找到左树的最右节点mR
（3）如果（2）中mR.right=null，则让mR.right=cur，cur=cur.left
（4）如果（2）中mR.right=cur,则让mR.right=null，然后cur=cur.right
//复习Morris遍历
public static void morrisReview(Node head){
if (head == null) return;
//【随时熟悉Morris遍历】**Morris遍历的流程：**
//（0）cur默认最开始指向head，mR默认为null【即cur左树的最右节点】，判断cur是否有左树？
Node cur = head;
Node mR = null;
while (cur != null){
//（1）cur如果**没有左树**，直接去右树cur=cur.right（当然没有右树那停止Morris遍历）
//没左树的，跟（4）联合精简代码
mR = cur.left;//mR走一步先
//（2）cur如果**有左树**，先找到**左树的最右节点mR**
if (mR != null){
while (mR.right != null && mR.right != cur) mR = mR.right;//往右穿
//（3）如果（2）中mR.right=null，则让mR.right=cur，cur=cur.left
if(mR.right == null){//打印cur，这是第1次见面
mR.right = cur;
cur = cur.left;
continue;//绕过（4）
}else {//打印cur，这是第2次见面
mR.right = null;//mR.right=cur,则让mR.right=null，然后cur=cur.right
}
}
//（1）cur如果**没有左树**，直接去右树cur=cur.right（当然没有右树那停止Morris遍历）
//（4）如果（2）中mR.right=cur,则让mR.right=null，然后cur=cur.right
cur = cur.right;//因为（3）那continue，不会来着，否则（1）和（4）都要来
//这里加不加else都行，但是先序打印可能需要加else，1面就要打印
}
}
利用Morris遍历求最小高度
暂时还不会，回头学会了再说……
总结
提示：重要经验：
1）笔试面试都先用常规树形DP搞二叉树的递归套路，收集信息，整理信息，这也算是最优解了
2）Morris遍历搞这个最小高度的难度非常大，控制高度增加减少，很麻烦
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。
