# Morris 遍历实现二叉树的遍历

CSDN：Morris 遍历实现二叉树的遍历

## 说明

Morris 遍历可以实现二叉树的先，中，后序遍历，且时间复杂度 O(N), 空间复杂度可以做到 O(1)

## Morris 遍历流程

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) {
return;
}
System.out.println("....morris order....");
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遍历实现先序遍历

    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) {
// 有右树，第一次来到自己就收集
mostRight.right = cur;
cur = cur.left;
continue;
} else {
// mostRight.right = cur;
mostRight.right = null;
}
} else {
// 没有右树的，来到就收集
}
cur = cur.right;
}
return ans;
}


## 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 {
// 来到自己两次的点，第二次来到才收集
mostRight.right = null;
}
} else {
// 只来到自己一次的点，来到就收集
}
cur = cur.right;
}
return ans;
}
}


## 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) {
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;
}


## 参考资料

Original: https://www.cnblogs.com/greyzeng/p/16791292.html
Author: Grey Zeng
Title: Morris 遍历实现二叉树的遍历

## Title: Python – pyradiomics – 邻域灰阶依赖性矩阵（Neighboring Gray Level Dependence Matrix）

### 文章目录

Sun C, Wee WG. Neighboring Gray Level Dependence Matrix for Texture Classification. Comput Vision, Graph Image Process. 1983;23:341-352

# 理论

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 ∣≤α

# ; 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]
])


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}
'''


dimension = 2
NGLDM = np.zeros((len(grey_levels_rank), 3 ** dimension))
print(NGLDM.shape)
'''
(7, 9)
'''


[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


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）

(0)

### 大家都在看

• #### Python：用argparse模块解析命令行选项

1. 用argparse模块解析命令行选项 我们在上一篇博客《Linux：可执行程序的Shell传参格式规范》中介绍了Linux系统Shell命令行下可执行程序应该遵守的传参规范（…

Python 2023年2月4日
018
• #### python股票价格涨跌幅_案例_如何计算股票复权价格

《邢不行-2019新版|Python股票量化投资课程》 author：邢不行 微信：xingbuxing0807 本节课讲解如何根据预测者网的历史数据，计算复权价格 import …

Python 2023年1月8日
040
• #### Docker安装MySQL并使用Navicat连接

MySQL简单介绍： MySQL 是一个开放源码的关系数据库管理系统，开发者为瑞典 MySQL AB 公司。目前 MySQL 被广泛地应用在 Internet 上的大中小型网站中。…

Python 2023年1月31日
019

文章目录 上传文件方式一： * 1.index.html文件： 2.主文件main.py: 上传文件方式二： * 1.index2.html文件： 2.main.py文件： 上传文…

Python 2023年1月2日
029
• #### 【玩转Scikit-learn】机器学习工程师的浅入深出保姆级学习成长指南+变强规划+入门教程~

💖作者简介：大家好，我是 车神哥，府学路18号的车神🥇⚡About—> 车神：从 寝室到 实验室最 快3分钟，最 慢3分半（那半分钟其实是等 红 绿 灯）📝个人主页：车手只需…

2022年8月22日
0187
• #### python 写csv加锁_利用python对csv的读写

利用pandas读写csv pandas写入csv import pandas as pd 任意的多组列表 a = [1,2,3] b = [4,5,6] 字典中的key值即为cs…

Python 2022年12月31日
056
• #### 5.1 Python基础

5.1 Python基础 1. Python入门 * 1.1 Python语言介绍 1.2 安装及配置 1.3 交互式编程 1.4 Python开发工具 2. 核心语法 * 2.1…

Python 2023年1月19日
019
• #### [深度学习] Python人脸识别库Deepface使用教程

deepface是一个Python轻量级人脸识别和人脸属性分析（年龄、性别、情感和种族）框架，提供非常简单的接口就可以实现各种人脸识别算法的应用。deepface官方仓库为deep…

2022年8月31日
0155
• #### pytest check可替代pytest.assume断言，且可展示出断言失败时的详细参数

需求：1.输入多组数据执行测试用例，断言每组数据符合预期2.执行所有测试数据，即使失败， 还是会继续执行3.测试数据参数化时，断言失败的数据有标记 针对问题1.一般用 pytest…

Python 2023年1月17日
050
• #### python微软雅黑_matplotlib中文显示-微软雅黑

网上的方法很多，但基本的方法都是片面的。 [En] There are many methods on the Internet, but the basic ones are o…

Python 2023年1月15日
054
• #### 在Python中如何修改字符串中的某一位字符？

python中字符串是不可变类型，即无法直接修改字符串的某一位字符。 例如想把’abc123’修改成’abcd23’，若执行下面代码…

Python 2022年8月31日
0156
• #### 7_JS关于数据代理_Object.defineProperty_Vue数据代理_双向绑定

1 背景 市面上常见的有，2pc/3pc、tcc、saga等常见的分布式事务解决方案，但是实际实施起来框架比较重，设计开发比较繁琐，不易于快速开发上手。本文提供一种基于柔性事务设计…

Python 2023年1月30日
014
• #### 在Python中运行gmssl

在Python中运行gmssl Python版本 gmssl介绍 安装gmssl包 基于gmssl的SM2、3、4算法实现 SM2算法 SM3算法 SM4算法 在Python中运行…

2022年8月14日
0225
• #### keyerror什么意思python_为什么会出现keyerror？

Python 2023年1月9日
058
• #### 【pytorch】错误：No module named ‘typing_extensions‘ 问题解决

前几天，奔跑模型发现上报了一个非常奇怪的错误，发现是源代码中的一个错误，有点离谱。 [En] A few days ago, the running model found tha…

2022年8月24日
0112
• #### 数据预处理时为什么要使用OneHot编码？

什么是LabelEncoder（整数编码） &#x6574;&#x6570;&#x7F16;&#x7801; 将一列文本数据转化成数值， 即列中的每…

Python 2023年2月2日
048