热门标签
热门文章
- 1RabbitMQ异步与重试机制_rabbitmq 重试机制测试
- 2四种经典限流算法的实现思路以及各自的优缺点_java的限流实现的各种优缺点
- 3Flink 实践教程-入门（10）：Python作业的使用_flink python
- 4C语言学生选课系统实现_学生选修课程系统设计c语言代码
- 5边缘计算加持下的智慧社区_智慧社区边缘计算
- 6Anaconda环境下安装 opencv_annocoda opencv
- 7思科实验9.网络层：PPP协议配置_思科ppp协议
- 8论文Word问题02：EndNoteX9_插入引用参考文献_endnotex9怎么引用参考文献
- 9zookeeper总结
- 10Mobile ALOHA 的模仿学习算法和协同训练--翻译斯坦福机器人项目1_mobile-aloha联合训练
当前位置: article > 正文
Morris遍历——二叉树遍历时间复杂度O(N)&额外空间复杂度O(1)_o(n)时间遍历树
作者：盐析白兔 | 2024-05-26 13:10:39
赞
踩
o(n)时间遍历树
package Morris
import (
"fmt"
"math"
"testing"
)
/*
morris 遍历，遍历完一棵二叉树，可以实现二叉树的先序中序后序，可以做到时间复杂度O(N),额外空间复杂度O(1)
笔试以最快Ac为目标，面试时候可以吹牛逼
kmp 的 morris 和 morris遍历中的morris 是一个人
二叉树的遍历，递归非递归都需要额外空间
时间复杂度 O(N) , 额外空间复杂度 O(h) 和高度相关
流程
当前节点cur，一开始 cur来到整棵树的头
1.如果cur 无左树，cur直接向右移动 cur = cur.Right
2.如果cur 有左树，找到cur左树最右节点 mostRight [ 。。。 .Right.Right....]
2.1 如果mostRight 的右指针指向nil， mostRight.Right = cur, cur = cur.Left 改指针走向
2.2 mostRight 的右指针 指向cur, mostRight.Right = nil , cur = cur.Right
3. cur = nil 时候， 循环结束
1
/ \
2 3
/ \ / \
4 5 6 7
忘掉先序，中序，后序概念
cur 依次到达每个节点的顺序 叫 morris序
------------------------------------------------------
1
/ \
2 3
/ \ / \
4 5 6 7
------------------------------------------------------
morris序： 1
有左树
1 < cur
/ \
2 3
/ \ / \
4 5 6 7
来到左树最右节点
------------------------------------------------------
morris序： 1 2
左树最右节点的右指针为nil
1 < cur
/ /| \
cur> 2 | 3
/ \ | / \
4 5 | 6 7
\__|
左树最右节点的右指针指向cur,cur 来到cur的 left
1
/ /| \
cur> 2 | 3
/ \ | / \
4 5 | 6 7
\__|
------------------------------------------------------
有左树
1
/ /| \
cur> 2 | 3
/ /|\ | / \
4 | 5 | 6 7
\__| \__|
来到左树最右节点，让左树最右节点的右指针指向cur
------------------------------------------------------
morris序： 1 2 4
1
/ /| \
2 | 3
/ /|\ | / \
cur> 4 | 5 | 6 7
\__| \__|
cur没有左树，cur向右移动，来到2，但是2已经被走过了
morris序： 1 2 4 2
1
/ /| \
cur> 2 | 3
/ /|\ | / \
4 | 5 | 6 7
\__| \__|
让右指针指向nil，cur往右移动,来到5
1
/ /| \
cur> 2 | 3
/ \ | / \
4 5 | 6 7
\ \__|
nil
1
/ /| \
cur> 2 | 3
/ \ | / \
4 5 | 6 7
/|\__|
|
cur
morris序： 1 2 4 2 5
cur 没有最右节点，来到1
1 <cur
/ /| \
cur> 2 | 3
/ \ | / \
4 5 | 6 7
\__|
morris序： 1 2 4 2 5 1
恢复5的右节点指向nil，cur 往右移动
1
/ \
2 3 <cur
/ \ / \
4 5 6 7
morris序： 1 2 4 2 5 1 3
1
/ \
2 3
/ \ / /| \
4 5 6 | 7
/|\_|
|
cur
morris序： 1 2 4 2 5 1 3 6
morris序： 1 2 4 2 5 1 3 6 3
1
/ \
2 3 <cur
/ \ / \
4 5 6 7
1
/ \
2 3
/ \ / \
4 5 6 7 <cur
morris序： 1 2 4 2 5 1 3 6 3 7
什么样的树都可以遍历完
任何一棵树，只要有左树，都会来到2次
没有左树的节点，只会来到1次
一个节点往右走，再也不会回来了
*/
type Node struct {
Value int
Left *Node
Right *Node
}
func morris(head *Node) {
if head == nil {
return
}
cur := head
var mostRight *Node
for cur != nil { // cur 不断往左或往右跳，一旦为空就出来
mostRight = cur.Left //cur 有没有左树
if mostRight != nil {
// 找到cur 左树上真实的最右节点
for mostRight.Right != nil && mostRight.Right != cur { // 第一次 nil， 第二次 cur
mostRight = mostRight.Right
}
// 从for中出来，mostRight 一定是cur左树上的最右节点
if mostRight.Right == nil {
mostRight.Right = cur
cur = cur.Left
continue // continue 最外层for
}else { // mostRight.Right != nil => mostRight.Right == cur
mostRight.Right = nil
}
}
cur = cur.Right
}
}
func TestMorris(t *testing.T) {
head := &Node{
Value: 1,
Left: &Node{
Value: 2,
Left: &Node{
Value: 4,
Left: nil,
Right: nil,
},
Right: &Node{
Value: 5,
Left: nil,
Right: nil,
},
},
Right: &Node{
Value: 3,
Left: &Node{
Value: 6,
Left: nil,
Right: nil,
},
Right: &Node{
Value: 7,
Left: nil,
Right: nil,
},
},
}
morrisPre(head)
morrisIn(head)
morrisPos(head)
}
// 先序 第一次来到节点的时候打印，第二次来到的时候不打印
// 中序 第二次来到节点的时候打印，能回到2次的不打印(有左树的)，第二次回归时打印，只能来到1次的直接打印(没有左树的)
// 后序 比较复杂
func morrisIn(head *Node) { //中序
if head == nil {
return
}
cur := head
var mostRight *Node
for cur != nil { // cur 不断往左或往右跳，一旦为空就出来
mostRight = cur.Left //cur 有没有左树
if mostRight != nil {
// 找到cur 左树上真实的最右节点
for mostRight.Right != nil && mostRight.Right != cur { // 第一次 nil， 第二次 cur
mostRight = mostRight.Right
}
// 从for中出来，mostRight 一定是cur左树上的最右节点
if mostRight.Right == nil {
mostRight.Right = cur
cur = cur.Left
continue // continue 最外层for
}else { // mostRight.Right != nil => mostRight.Right == cur
mostRight.Right = nil
}
}
fmt.Print(cur.Value , "\t")
cur = cur.Right
}
fmt.Println()
}
func morrisPre(head *Node) { //先序
if head == nil {
return
}
cur := head
var mostRight *Node
for cur != nil { // cur 不断往左或往右跳，一旦为空就出来
mostRight = cur.Left //cur 有没有左树
if mostRight != nil {
// 找到cur 左树上真实的最右节点
for mostRight.Right != nil && mostRight.Right != cur { // 第一次 nil， 第二次 cur
mostRight = mostRight.Right
}
// 从for中出来，mostRight 一定是cur左树上的最右节点
if mostRight.Right == nil {
mostRight.Right = cur
fmt.Print(cur.Value,"\t")
cur = cur.Left
continue // continue 最外层for
}else { // mostRight.Right != nil => mostRight.Right == cur
mostRight.Right = nil
}
} else {
fmt.Print(cur.Value,"\t")
}
cur = cur.Right
}
fmt.Println()
}
// 打印时机，就放在能回到自己两次，且第二次回到自己的时候
// 打印他左树的右边界，逆序打印
// 整棵树可以被子树的右边界分解掉
// 不能放到栈里，用 [ 反转链表 ] 打印完再调回来 时间复杂度O(N)
func morrisPos(head *Node) { //后序
if head == nil {
return
}
cur := head
var mostRight *Node
for cur != nil { // cur 不断往左或往右跳，一旦为空就出来
mostRight = cur.Left //cur 有没有左树
if mostRight != nil {
// 找到cur 左树上真实的最右节点
for mostRight.Right != nil && mostRight.Right != cur { // 第一次 nil， 第二次 cur
mostRight = mostRight.Right
}
// 从for中出来，mostRight 一定是cur左树上的最右节点
if mostRight.Right == nil {
mostRight.Right = cur
cur = cur.Left
continue // continue 最外层for
}else { // mostRight.Right != nil => mostRight.Right == cur
mostRight.Right = nil
printEdge(cur.Left)
}
}
cur = cur.Right
}
printEdge(head)
fmt.Println()
}
// 线索二叉树
func printEdge(head *Node) {
tail := reverseEdge(head)
cur := tail
for cur != nil {
fmt.Print(cur.Value, "\t")
cur = cur.Right
}
reverseEdge(tail)
}
func reverseEdge(from *Node) *Node {
var pre, next *Node
for from != nil {
next = from.Right
from.Right = pre
pre = from
from = next
}
return pre
}
/*
扩展： 判断一棵树是不是搜索二叉树
*/
//任何一个节点左树头节点比自己小，右树头节点比自己大
func morrisIsBST(head *Node) bool {
if head == nil {
return true
}
cur := head
var mostRight *Node
pre := (*int)(nil)
for cur != nil { // cur 不断往左或往右跳，一旦为空就出来
mostRight = cur.Left //cur 有没有左树
if mostRight != nil {
// 找到cur 左树上真实的最右节点
for mostRight.Right != nil && mostRight.Right != cur { // 第一次 nil， 第二次 cur
mostRight = mostRight.Right
}
// 从for中出来，mostRight 一定是cur左树上的最右节点
if mostRight.Right == nil {
mostRight.Right = cur
cur = cur.Left
continue // continue 最外层for
}else { // mostRight.Right != nil => mostRight.Right == cur
mostRight.Right = nil
}
}
if pre != nil && *pre >= cur.Value {
return false
}
*pre = cur.Value
cur = cur.Right
}
return true
}
/*
一棵二叉树，所有叶节点到头部距离最短的(二叉树的最小高度)
*/
/*
方法1，二叉树的递归套路
*/
func minHeight1(head *Node) int {
if head == nil {
return 0
}
return p(head)
}
func p(x *Node) int {
if x.Left == nil && x.Right == nil {
return 1
}
//左右子树起码有一个不为空
leftH := math.MinInt
if x.Left != nil {
leftH = p(x.Left)
}
rightH := math.MaxInt
if x.Right != nil {
rightH = p(x.Right)
}
return 1 + Min(leftH,rightH)
}
func Min(a, b int) int {
if a > b {
return b
}
return a
}
/*
整个过程用有限几个变量
1 cur 高度
2 cur 此时是叶节点，记录一下高度， Min(min, curH)
*/
func minHeight2forMorris(head *Node) int {
if head == nil {
return 0
}
cur := head
var mostRight *Node
curLevel := 0
minHeight := math.MaxInt
for cur != nil { // cur 不断往左或往右跳，一旦为空就出来
mostRight = cur.Left // cur 有没有左树
if mostRight != nil {
rightBoardSize := 1
// 找到cur 左树上真实的最右节点
for mostRight.Right != nil && mostRight.Right != cur { // 第一次 nil， 第二次 cur
rightBoardSize++
mostRight = mostRight.Right
}
// 从for中出来，mostRight 一定是cur左树上的最右节点
if mostRight.Right == nil { // 第一次到达
curLevel++
mostRight.Right = cur
cur = cur.Left
continue // continue 最外层for
}else { // mostRight.Right != nil => mostRight.Right == cur
//第二次到达
if mostRight.Left == nil {
minHeight = Min(minHeight,curLevel)
}
curLevel -= rightBoardSize
mostRight.Right = nil
}
}else { // 只有一次到达
curLevel++
}
cur = cur.Right
}
finalRight := 1
cur = head
for cur.Right != nil {
finalRight++
cur = cur.Right
}
if cur.Left == nil && cur.Right == nil {
minHeight = Min(minHeight,finalRight)
}
return minHeight
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
- 337
- 338
- 339
- 340
- 341
- 342
- 343
- 344
- 345
- 346
- 347
- 348
- 349
- 350
- 351
- 352
- 353
- 354
- 355
- 356
- 357
- 358
- 359
- 360
- 361
- 362
- 363
- 364
- 365
- 366
- 367
- 368
- 369
- 370
- 371
- 372
- 373
- 374
- 375
- 376
- 377
- 378
- 379
- 380
- 381
- 382
- 383
- 384
- 385
- 386
- 387
- 388
- 389
- 390
- 391
- 392
- 393
- 394
- 395
- 396
- 397
- 398
- 399
- 400
- 401
- 402
- 403
- 404
- 405
- 406
- 407
- 408
- 409
- 410
- 411
- 412
- 413
- 414
- 415
- 416
- 417
- 418
- 419
- 420
- 421
- 422
- 423
- 424
- 425
- 426
- 427
- 428
- 429
- 430
- 431
- 432
- 433
- 434
- 435
- 436
- 437
- 438
- 439
- 440
- 441
- 442
- 443
- 444
- 445
- 446
- 447
- 448
- 449
- 450
- 451
- 452
- 453
- 454
- 455
- 456
- 457
- 458
- 459
- 460
- 461
- 462
- 463
- 464
- 465
- 466
- 467
- 468
- 469
- 470
- 471
- 472
- 473
- 474
- 475
- 476
- 477
- 478
- 479
- 480
- 481
- 482
- 483
- 484
- 485
- 486
- 487
- 488
- 489
- 490
- 491
- 492
- 493
- 494
- 495
- 496
- 497
- 498
- 499
- 500
- 501
- 502
- 503
- 504
- 505
- 506
- 507
- 508
- 509
- 510
- 511
- 512
- 513
- 514
- 515
- 516
- 517
- 518
- 519
- 520
- 521
- 522
- 523
- 524
- 525
- 526
- 527
- 528
- 529
- 530
- 531
- 532
- 533
- 534
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/626803
推荐阅读
相关标签
