Morris 遍历实现二叉树的遍历
作者：Grey
原文地址：
说明
Morris 遍历可以实现二叉树的先，中，后序遍历，且时间复杂度 O(N), 空间复杂度可以做到 O(1)。
Morris 遍历流程
假设有一棵如下的二叉树
Morris遍历的流程主要分如下几个步骤：
第一步，从头节点开始遍历。
第二步，假设当前遍历的节点是 cur。
第三步，如果 cur无左树, cur来到其右树上，即： cur = cur.right
第四步，如果 cur有左树，找到 cur左树最右节点，假设叫 mostRight，则有如下两种小情况：
情况1，如果 mostRight的右指针指向空, 则将 mostRight的右指针指向 cur，即： mostRight.right = cur, 然后将 cur向左移动，即： cur = cur.left，
情况2，如果 mostRight的右指针指向当前节点 cur，则将 mostRight的右指针指向空，即： mostRight.right = null，然后将 cur向右移动，即： cur = cur.right。
第五步：当 cur = null，遍历结束。
根据如上流程，示例二叉树的Morris遍历序列为：
1-->2-->4-->7-->11-->7-->4-->8-->12-->8-->1-->3-->5-->3-->6-->9-->13-->6-->10
Morris遍历可以实现在 O(N)时间复杂度内，用 O(1)的空间复杂度实现对树的遍历，而且， 只要某个节点有右树，则这个节点一定会被遍历两次，我们可以通过Morris遍历来实现二叉树的先，中，后序遍历，做到时间复杂度 O(N)，空间复杂度 O(1)。
代码实现如下：
public class Code_Morris {
//当前是cur
//1. cur无左树,cur = cur.right
//2. cur有左树,找到左树最右节点mostRight
// a. mostRight的右指针指向null, mostRight.right = cur, cur = cur.right
// b. mostRight的右指针指向当前节点cur，mostRight.right = null, cur = cur.right
//3. cur = null 停
public static void morrisPrint(TreeNode head) {
if (head == null) {
return;
}
System.out.println("....morris order....");
TreeNode cur = head;
System.out.print(cur.val + "-->");
TreeNode mostRight;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
System.out.print(cur.val + "-->");
continue;
} else {
mostRight.right = null;
}
}
cur = cur.right;
if (cur != null) {
System.out.print(cur.val + "-->");
}
}
}
}
Morris遍历实现先序遍历
根据Morris的遍历结果，没有右树的点只会遍历一次，有右树的点会遍历两次，针对遍历一次的点，遍历到就收集，针对遍历两次的点，第一次遍历到就收集，第二次遍历到不收集，整个流程跑完，则得到了先序遍历的结果。
代码如下：
public static List preorderTraversal(TreeNode root) {
if (null == root) {
return new ArrayList<>();
}
List ans = new ArrayList<>();
TreeNode mostRight;
TreeNode cur = root;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
// 有右树，第一次来到自己就收集
ans.add(cur.val);
mostRight.right = cur;
cur = cur.left;
continue;
} else {
// mostRight.right = cur;
mostRight.right = null;
}
} else {
// 没有右树的，来到就收集
ans.add(cur.val);
}
cur = cur.right;
}
return ans;
}
测评链接：LeetCode 144. Binary Tree Preorder Traversal
Morris遍历实现中序遍历
针对遍历一次的点，遍历到就收集，针对遍历两次的点，第一次遍历到不收集，第二次遍历才收集，整个流程跑完，则得到了中序遍历的结果。
代码如下：
class Solution {
public List inorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List ans = new ArrayList<>();
TreeNode mostRight;
TreeNode cur = root;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
} else {
// 来到自己两次的点，第二次来到才收集
ans.add(cur.val);
mostRight.right = null;
}
} else {
// 只来到自己一次的点，来到就收集
ans.add(cur.val);
}
cur = cur.right;
}
return ans;
}
}
测评链接：LeetCode 94. Binary Tree Inorder Traversal
Morris遍历实现后序遍历
Morris遍历实现后序遍历相对比较麻烦，处理时机只放在 能回到自己两次的点，能回到自己两次的点在第二次回到自己的时刻，不打印它自己，而是逆序打印他左树的右边界, 整个遍历结束后，单独逆序打印整棵树的右边界，即得到了后序遍历的结果。
代码如下：
public List postorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List ans = new ArrayList<>();
TreeNode cur = root;
TreeNode mostRight;
while (cur != null) {
mostRight = cur.left;
if (mostRight != null) {
while (mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if (mostRight.right == null) {
mostRight.right = cur;
cur = cur.left;
continue;
} else {
mostRight.right = null;
// 第二次来到自己的时候，收集自己的左树的右边界
collect(cur.left, ans);
}
}
cur = cur.right;
}
collect(root, ans);
return ans;
}
private void collect(TreeNode root, List ans) {
TreeNode node = reverse(root);
TreeNode c = node;
while (c != null) {
ans.add(c.val);
c = c.right;
}
reverse(node);
}
private TreeNode reverse(TreeNode node) {
TreeNode pre = null;
TreeNode cur = node;
while (cur != null) {
TreeNode t = cur.right;
cur.right = pre;
pre = cur;
cur = t;
}
return pre;
}
需要注意两点：
第一点， collect方法即逆序收集左树的有边界，由于每个节点没有指向父的指针，所以，要实现逆序，需要针对右边界采用反转链表的方式。即 reverse函数的逻辑。
第二点，在 collect方法调用完反转链表操作后，还要还原整个右边界。否则整棵树的指针就指乱了。
测评链接：LeetCode 145. Binary Tree Postorder Traversal
更多
参考资料
Original: https://www.cnblogs.com/greyzeng/p/16791292.html
Author: Grey Zeng
Title: Morris 遍历实现二叉树的遍历
相关阅读
Title: Python – pyradiomics – 邻域灰阶依赖性矩阵（Neighboring Gray Level Dependence Matrix）
文章目录
有关邻域灰阶依赖性矩阵（Neighboring Gray Level Dependence Matrix, NGLDM）的一切的起源：
Sun C, Wee WG. Neighboring Gray Level Dependence Matrix for Texture Classification. Comput Vision, Graph Image Process. 1983;23:341-352
参考文件：
https://pyradiomics.readthedocs.io/en/latest/features.html#module-radiomics.gldm
理论
对于两个像素依赖性的判断，是基于他们的距离和他们像素值的差异得到的。对于某一个像素点，其像素值为L0，在与它距离delta范围内的像素中，如果某个像素点的像素值L1与它相差不超过alpha，则判断周围像素L1依赖于中心像素L0，即
L 1 i s d e p e n d e n t o n L 0 i f ∣ L 1 − L 0 ∣ ≤ α L1\ is\ dependent\ on\ L0\ if\ |L1-L0|\le\alpha L 1 i s d e p e n d e n t o n L 0 i f ∣L 1 −L 0 ∣≤α
在pyradiomics源码中，delta默认取值为1，alpha默认取值为0，即中心像素点周围8个像素（或26个像素）中，和中心像素值相同的，判断为依赖于中心像素。
以一个二维图像 I 为例：
它的NGLDM为：
以第五行为例，4和2表示在像素值等于从小到大第五个像素值的像素中，有4个像素周围没有和自己相同的像素，有2个像素周围有一个和自己相同的像素。
设行数为i，列数为j，图像中灰阶构成一维数组N_g，P(i, j)表示像素值等于N_g(i)、周围有j-1个依赖像素的像素的个数。
; Python实操
创建图像矩阵
import numpy as np
img_array = np.array([
[5, 2, 5, 4, 4, 6, 8],
[3, 3, 3, 1, 3, 2, 5],
[2, 1, 1, 2, 6, 1, 3],
[4, 2, 2, 1, 8, 2, 3],
[3, 5, 1, 2, 3, 3, 2],
[5, 2, 8, 3, 4, 1, 6],
[2, 6, 2, 6, 3, 5, 2]
])
计算NGLDM的第一步，是将所有像素值从小到大排列，获得每个像素值的索引， I 中没有像素值为7的点，因此像素值为8的点的索引值是第7个：
grey_levels = np.unique(img_array)
grey_levels_rank = dict(zip(grey_levels, range(len(grey_levels))))
print(grey_levels)
print(grey_levels_rank)
'''
[1 2 3 4 5 6 8]
{1: 0, 2: 1, 3: 2, 4: 3, 5: 4, 6: 5, 8: 6}
'''
初始化NGLDM矩阵
dimension = 2
NGLDM = np.zeros((len(grey_levels_rank), 3 ** dimension))
print(NGLDM.shape)
'''
(7, 9)
'''
开始填充NGLDM矩阵，不追求速度的方法，就是从(1, 1)点开始遍历每个像素值Li，先求的它周围的像素点的坐标，然后计算有多少个依赖于它n，然后在NGLDM第i行第n列处+1
设一个点坐标为(x, y)，那在二维平面内，它周围delta = 1的点为：
定义一个返回周围像素坐标的函数
[En]
Define a function that returns the coordinates of the surrounding pixels
def surrounding_2d(x, y):
surroundings = [
(x - 1, y - 1), (x, y - 1), (x + 1, y - 1),
(x - 1, y), (x + 1, y),
(x - 1, y + 1), (x, y + 1), (x + 1, y + 1)
]
return surroundings
开始遍历：
alpha = 0
for x in range(img_array.shape[0]):
for y in range(img_array.shape[1]):
dependence = 0
for (x_s, y_s) in surrounding_2d(x,y):
if (0 x_s < img_array.shape[0]) and (0 y_s < img_array.shape[1]):
if abs(img_array[x_s, y_s] - img_array[x, y]) alpha:
dependence += 1
NGLDM[grey_levels_rank[img_array[x, y]], dependence] += 1
然后就得到NGLDM了~
print(NGLDM)
'''
[[2. 3. 1. 1. 0. 0. 0. 0. 0.]
[3. 7. 2. 1. 0. 0. 0. 0. 0.]
[2. 4. 5. 0. 0. 0. 0. 0. 0.]
[2. 2. 0. 0. 0. 0. 0. 0. 0.]
[4. 2. 0. 0. 0. 0. 0. 0. 0.]
[5. 0. 0. 0. 0. 0. 0. 0. 0.]
[3. 0. 0. 0. 0. 0. 0. 0. 0.]]
'''
Original: https://blog.csdn.net/qq_48321729/article/details/123317675
Author: Doct.Y
Title: Python – pyradiomics – 邻域灰阶依赖性矩阵（Neighboring Gray Level Dependence Matrix）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/363519/
转载文章受原作者版权保护。转载请注明原作者出处！
