Rust实现Morris遍历(中序、前序、后序) | Peanuts' Blog

Rust实现Morris遍历(中序、前序、后序)

前言

尝试用Rust实现了Morris遍历算法,写出来确实有点乱七八糟,各种clone()unwrap()borrow(),实在是辣眼睛!然后@upsuper看不下去了并给出了大量使用Iterator的优化版本:
morris_traversal.rs

在这里表示感谢!

二叉树

定义

这里选择来自LeetCode的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode {
val,
left: None,
right: None
}
}
}

补充函数

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
impl TreeNode{
#[inline]
pub fn from_vec(nums: Vec<i32>)->Option<Rc<RefCell<TreeNode>>>{
if nums.len()==0{
return None;
}
let head = Some(Rc::new(RefCell::new(TreeNode::new(nums[0]))));
let mut queue: Vec<Option<Rc<RefCell<TreeNode>>>> = Vec::new();
queue.push(head.clone());

let mut i=1;
while i < nums.len(){
if !queue.is_empty(){
if let Some(node)=queue.remove(0) {
let mut node = node.borrow_mut();
if nums[i]!=-1{
// println!("{}",i);
node.left=Some(Rc::new(RefCell::new(TreeNode::new(nums[i]))));
queue.push(node.left.clone());
}
i+=1;
if i==nums.len(){
break;
}
if nums[i]!=-1{
node.right=Some(Rc::new(RefCell::new(TreeNode::new(nums[i]))));
queue.push( node.right.clone());
}
i+=1;

}
}else {
break;
}
}
head
}

#[inline]
pub fn into_vec(root: Option<Rc<RefCell<TreeNode>>>)->Vec<i32>{
let mut nums: Vec<i32>=Vec::new();
if let Some(root)= root{
let mut queue:Vec<Option<Rc<RefCell<TreeNode>>>> =Vec::new();
queue.push(Some(root).clone());
while !queue.is_empty(){
let node =queue.remove(0);
if node !=None{
let node = node.unwrap();
let node=node.borrow();
nums.push(node.val);
// 叶子结点自动被过滤
if !(node.left==None && node.right==None ) {
// println!("{:?},{:?}",node.left,node.right);
queue.push(node.left.clone());
queue.push(node.right.clone());
}
}else {
nums.push(-1);
}
}
}
nums
}

Morris遍历

Morris中序遍历

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
impl TreeNode{
pub fn inorder_morris_traversal(root: Option<Rc<RefCell<TreeNode>>>) ->Vec<i32> {
// 1. 如果当前节点的左孩子为空,则**输出当前节点**并将其右孩子作为当前节点。
// 2. 如果当前节点的左孩子不为空,在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
// a) 如果前驱节点的右孩子为空,将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
// b) 如果前驱节点的右孩子为当前节点,将它的右孩子重新设为空(恢复树的形状)。**输出当前节点**。当前节点更新为当前节点的右孩子。
let mut nums: Vec<i32> = Vec::new();
let mut prev: Option<Rc<RefCell<TreeNode>>> = None;
let mut curr: Option<Rc<RefCell<TreeNode>>> = root;
while curr != None {
if curr.as_ref().unwrap().borrow().left == None { //1
nums.push(curr.as_ref().unwrap().borrow().val);
curr =curr.clone().unwrap().borrow().right.clone();
}else{ //2
prev=curr.clone().as_ref().unwrap().borrow().left.clone();

while prev.as_ref().unwrap().borrow().right!=None && prev.as_ref().unwrap().borrow().right!=curr {
prev=prev.clone().unwrap().borrow().right.clone();
}

if prev.as_ref().unwrap().borrow().right==None{ //2.a
prev.unwrap().borrow_mut().right=curr.clone();
curr=curr.unwrap().borrow().left.clone();
}else{ //2.b
prev.as_ref().unwrap().borrow_mut().right=None;
nums.push(curr.as_ref().unwrap().borrow().val);
curr =curr.clone().unwrap().borrow().right.clone();
}
}
}
nums
}
}

Morris前序遍历

注意比较和中序遍历的差别

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
impl TreeNode{
#[inline]
pub fn preorder_morris_traversal(root: Option<Rc<RefCell<TreeNode>>>) ->Vec<i32> {
// 1. 如果当前节点的左孩子为空,则**输出当前节点**并将其右孩子作为当前节点。
// 2. 如果当前节点的左孩子不为空,在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
// a) 如果前驱节点的右孩子为空,将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。**输出当前节点**。
// b) 如果前驱节点的右孩子为当前节点,将它的右孩子重新设为空(恢复树的形状)。当前节点更新为当前节点的右孩子。
let mut nums: Vec<i32> = Vec::new();
let mut prev: Option<Rc<RefCell<TreeNode>>> = None;
let mut curr: Option<Rc<RefCell<TreeNode>>> = root;
while curr != None {
if curr.as_ref().unwrap().borrow().left == None { //1
nums.push(curr.as_ref().unwrap().borrow().val);
curr =curr.clone().unwrap().borrow().right.clone();
}else{ //2

prev=curr.clone().as_ref().unwrap().borrow().left.clone();

while prev.as_ref().unwrap().borrow().right!=None && prev.as_ref().unwrap().borrow().right!=curr {
prev=prev.clone().unwrap().borrow().right.clone();
}


if prev.as_ref().unwrap().borrow().right==None{ //2.a
nums.push(curr.as_ref().unwrap().borrow().val);
prev.unwrap().borrow_mut().right=curr.clone();
curr=curr.unwrap().borrow().left.clone();
}else{ //2.b
prev.as_ref().unwrap().borrow_mut().right=None;
curr =curr.clone().unwrap().borrow().right.clone();
}
}
}
nums
}
}

Morris后序遍历

相对于前序遍历,后序遍历则麻烦许多。这里的空间复杂度已经不再是O(1),因为push_reverse()Vec的使用。
思路来自Morris Traversal方法遍历二叉树(非递归,不用栈,O(1)空间)

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
impl TreeNode{
pub fn postorder_morris_traversal(root: Option<Rc<RefCell<TreeNode>>>) ->Vec<i32> {
// 翻转链表实现
fn push_reverse(from: Option<Rc<RefCell<TreeNode>>>,to: Option<Rc<RefCell<TreeNode>>>,nums: &mut Vec<i32>){
let mut tmp:Vec<i32> = Vec::new();
let mut from =from.clone();
tmp.push(from.as_ref().unwrap().borrow().val);
if from==to {
nums.push(from.as_ref().unwrap().borrow().val);
return;
}
while from!=to{
from=from.clone().unwrap().borrow().right.clone();
tmp.push(from.as_ref().unwrap().borrow().val);
}
while !tmp.is_empty(){
nums.push(tmp.pop().unwrap());
}
}
// 设置当前节点为临时结点
// 1. 如果当前节点的左孩子为空,则将其右孩子作为当前节点。
// 2. 如果当前节点的左孩子不为空,在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
// a) 如果前驱节点的右孩子为空,将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
// b) 如果前驱节点的右孩子为当前节点,将它的右孩子重新设为空(恢复树的形状)。**倒序输出当前节点左孩子到前序结点的所有节点**当前节点更新为当前节点的右孩子。
let mut nums: Vec<i32> = Vec::new();
let mut prev: Option<Rc<RefCell<TreeNode>>> = None;
let mut curr: Option<Rc<RefCell<TreeNode>>> = Some(Rc::new(RefCell::new(TreeNode::new(0))));
curr.as_ref().unwrap().borrow_mut().left=root;
while curr != None {
if curr.as_ref().unwrap().borrow().left == None { //1
curr =curr.clone().unwrap().borrow().right.clone();
}else{ //2
// 寻找前序节点
prev=curr.clone().as_ref().unwrap().borrow().left.clone();
while prev.as_ref().unwrap().borrow().right!=None && prev.as_ref().unwrap().borrow().right!=curr {
prev=prev.clone().unwrap().borrow().right.clone();
}

if prev.as_ref().unwrap().borrow().right==None{ //2.a
prev.unwrap().borrow_mut().right=curr.clone();
curr=curr.unwrap().borrow().left.clone();
}else{ //2.b
push_reverse(curr.as_ref().unwrap().borrow().left.clone(),prev.clone(),&mut nums);
prev.as_ref().unwrap().borrow_mut().right=None;
curr =curr.clone().unwrap().borrow().right.clone();
}
}
}
nums
}
}

测试

main.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
fn main(){
print!("Morris中序遍历:");
let nums =vec![6,2,7,1,4,-1,9,-1,-1,3,5,8,-1];
let head =TreeNode::from_vec(nums);
let nums=TreeNode::inorder_morris_traversal(head);
println!("{:?}",nums);

print!("Morris先序遍历:");
let nums =vec![1,2,7,3,4,-1,8,-1,-1,5,6,9,-1];
let head =TreeNode::from_vec(nums);
let nums=TreeNode::preorder_morris_traversal(head);
println!("{:?}",nums);

print!("Morris后序遍历:");
let nums =vec![9,5,8,1,4,-1,7,-1,-1,2,3,6,-1];
let head =TreeNode::from_vec(nums);
let nums=TreeNode::postorder_morris_traversal(head);
println!("{:?}",nums);
}

输出

1
2
3
Morris中序遍历:[1, 2, 3, 4, 5, 6, 7, 8, 9]
Morris先序遍历:[1, 2, 3, 4, 5, 6, 7, 8, 9]
Morris后序遍历:[1, 2, 3, 4, 5, 6, 7, 8, 9]

总结

虽然Morris遍历大量利用空结点,节省空间时间,空间复杂度:O(1),时间复杂度:O(n)。但是在效率极低的Rust的链表上,空间是不可能是O(1)的,所以最后翻转链表也就没有采用时间复杂度为O(n)的做法。总结一下,因为借用规则和所有权的存在,Rust的链表是真的低效