Peanuts' Blog

Keep Learning

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

Posted on Edited on In
Symbols count in article: 7.7k Reading time ≈ 7 mins.

前言

尝试用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的链表是真的低效