0%

Morris遍历

Morris遍历(节省空间)

Morris遍历

Morris遍历的核心思想就是利用树的大量空闲指针,实现空间的极限缩减

二叉树前序遍历

前序遍历规则如下:

  1. 新建临时节点,令该节点为root
  2. 如果当前节点的左子节点为空,将当前节点加入答案,并且遍历当前节点的右子节点
  3. 如果当前节点的左子节点不为空,在当前节点的左子树中找到当前节点在中序遍历下的前驱节点
    1. 如果前驱节点的右子节点为空,将前驱节点的右子节点设置为当前节点。然后将当前节点加入答案,并将前驱节点的右子节点更新为当前节点。当前节点更新为其左子节点。
    2. 如果前驱节点的右子节点为当前节点,将它的右子节点重新设空。当前节点更新为当前节点的右子节点。
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
import java.util.ArrayList;
import java.util.List;

/*
* @lc app=leetcode.cn id=144 lang=java
*
* [144] 二叉树的前序遍历
*/

// @lc code=start
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();

if(root == null){
return ans;
}
TreeNode p1 = root;
TreeNode p2 = null;
while(p1 != null){
p2 = p1.left;
if(p2 != null){
while(p2.right != null && p2.right != p1){
p2 = p2.right;
}
if(p2.right == null){
ans.add(p1.val);
p2.right = p1;
p1 = p1.left;
continue;
}else{
p2.right = null;
}
}else{
ans.add(p1.val);
}
p1 = p1.right;
}
return ans;
}
}
// @lc code=end

二叉树中序遍历

假设当前遍历到的节点为x:

  1. 如果x无左孩子,先将x的值加入答案数组,再访问x的右孩子,即x = x.right.
  2. 如果x有左孩子,则找到x左子树上的最右节点(即左子树中序遍历的最后节点,x在中序遍历的前驱节点),记为predecessor
    • 如果predecessor的右孩子为空,则将其右孩子指向x,然后访问x的左孩子,x = x.left.
    • 如果predecessor的右孩子不为空,则此时它的右孩子指向x,说明遍历完x的左子树,此时将predecessor右孩子置空,将x的值加入答案数组,然后访问x的右孩子,x = x.right
1
2


二叉树后序遍历

二叉树层序遍历

-------------本文结束感谢您的阅读-------------