二叉树算法大盘点( 三 ) _二叉树算法

文章插图
莫里斯遍历（Morris）
通常我们对于二叉树进行遍历时，使用递归遍历或是基于栈来遍历，这两种方法都拥有最差为O(n)的空间复杂度(递归方法会在递归调用上浪费更多的时间)，以及O(n)的时间复杂度。对于时间复杂度来说，由于需要遍历每个元素一次，所以O(n)已是最优情况。如此只能对空间进行优化。Morris遍历如何做到的呢？首先我们需要分析递归和基于栈的遍历它们为什么有O(n)的空间占用。以下图这个简单的二叉树遍历为例：

文章插图
例如进行中序遍历(LDR)，从1开始：

1有左孩子2，将1放入栈中，移动到节点2；
2有左孩子4，将2放入栈中，移动到节点4；
4左孩子为空，输出节点4，此时节点4右孩子也为空，弹栈回到节点2；
输出节点2，节点2有右孩子5，移动到节点5；
5左孩子为空，输出节点5，此时节点5右孩子也为空，弹栈回到节点1；

…
从上面分析可以得知，传统遍历利用空间存储未实现全部操作的父节点，比如对于1节点，一开始进行L操作，没有进行D、R操作所以需要存储起来。为解决这一问题，Morris算法用到了”线索二叉树”的概念，利用叶节点的左右空指针指向某种遍历顺序的前驱节点或后继节点。Morris算法中序遍历流程：

设置节点1为Current节点；
Current节点不为空，且有左孩子，于是找到节点1左子树中的最右侧节点，即节点5，使其右孩子指针指向自己，即link1；
Current节点移动到左孩子节点2，并删除父节点的左指针，使其指向为，即删除erase1；
节点2不为空，且有左孩子，于是找到节点2左子树中最右侧节点，即节点4，使其右孩子指针指向自己，即link2；
Current节点移动到左孩子节点4，并删除父节点的左指针，使其指向为，即删除erase2；
节点4左孩子为空，输出节点4，移动到右孩子节点2；
节点2无左孩子(指针指向)，输出节点2，移动到右孩子节点5；
节点5无左孩子，输出节点5，移动到右孩子节点1；
节点2无左孩子(指针指向)，输出节点1，移动到右孩子节点3；
…

文章插图
代码实现：
void Morris_inorderTraversal(TreeNode root) {TreeNode curr = root;TreeNode pre;while (curr != ) {if (curr.left == ) { // 左孩子为空System.out.print(curr.val+" ");curr = curr.right;}else { // 左孩子不为空// 找左子树中的最右节点pre = curr.left;while (pre.right != ) {pre = pre.right;}// 删除左孩子，防止循环pre.right = curr;TreeNode temp = curr;curr = curr.left;temp.left = ;}}}

文章插图
AVL树
AVL 树是一种平衡二叉树，平衡二叉树递归定义如下：

左右子树的高度差小于等于 1 。
其每一个子树均为平衡二叉树。

为了保证二叉树的平衡，AVL 树引入了所谓监督机制，就是在树的某一部分的不平衡度超过一个阈值后触发相应的平衡操作。保证树的平衡度在可以接受的范围内。既然引入了监督机制，我们必然需要一个监督指标，以此来判断是否需要进行平衡操作。这个监督指标被称为“平衡因子（Balance Factor）” 。定义如下：

平衡因子：某个结点的左子树的高度减去右子树的高度得到的差值。

基于平衡因子，我们就可以这样定义 AVL 树。

AVL 树：所有结点的平衡因子的绝对值都不超过 1 的二叉树。

为了计算平衡因子，我们自然需要在节点中引入高度这一属性。在这里，我们把节点的高度定义为其左右子树的高度的最大值。因此，引入了高度属性的 AVL 树的节点定义如下：
public class TreeNode {int val;int height;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}这里的节点和上面的不同的地方在于，我们多加了一个高度，用来记录每个节点的高度，如何得到每个节点的高度很简单，前面讲的算法中任何一种思路都可以实现，我这里就不赘述了，不过这里要多说一点的是，与之对应地，我们在进行如下操作时需要更新受影响的所有节点的高度：