Rust 二叉树遍历---- DFS 和 BFS

1. 树的定义

use std::rc::Rc;
use std::cell::RefCell;
// Definition for a binary tree node.
#[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

---

2. BFS

以下是二叉树前中后序遍历的 Rust 代码，利用栈实现，通过增加是否访问过的标记，能够以统一的写法实现，唯一的区别就是入栈的顺序。

2.1 前序遍历

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        // 前序：根-左-右，入栈顺序：右-左-根
        // tuple.0 - node, tuple.1 - visited
        let mut stack: Vec<(Option<Rc<RefCell<TreeNode>>>, bool)> = vec![];
        stack.push((root, false));
        let mut ans: Vec<i32> = vec![];
        while !stack.is_empty() {
            let curr_pair = stack.pop().unwrap();
            let visited = curr_pair.1;
            if let Some(node) = curr_pair.0.clone() {
                let node = node.borrow();
                if visited {
                    ans.push(node.val);
                } else {
                    if node.right != None {
                        stack.push((node.right.clone(), false));
                    }
                    if node.left != None {
                        stack.push((node.left.clone(), false));
                    }
                    stack.push((curr_pair.0, true));
                }
                
            }
        }
        ans
    }
}
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

2.2 中序遍历

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        // 中序遍历：左-根-右，入栈顺序：右-根-左
        // tuple.0 - node, tuple.1 - visite
        let mut stack: Vec<(Option<Rc<RefCell<TreeNode>>>, bool)> = vec![];
        stack.push((root, false));
        let mut ans = vec![];

        while !stack.is_empty() {
            let curr_pair = stack.pop().unwrap();
            let visited = curr_pair.1;
            if let Some(node) = curr_pair.0.clone() {
                let node = node.borrow();
                if visited {
                    ans.push(node.val);
                } else {
                    if node.right != None {
                        stack.push((node.right.clone(), false));
                    }

                    stack.push((curr_pair.0, true));

                    if node.left != None {
                        stack.push((node.left.clone(), false));
                    }
                }
            }
        }

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

2.3 后序遍历

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        // 后序遍历：左-右-根，入栈顺序：根-右-左
        // tuple.0 - node, tuple.1 - visite
        let mut stack: Vec<(Option<Rc<RefCell<TreeNode>>>, bool)> = vec![];
        stack.push((root, false));
        let mut ans: Vec<i32> = vec![];

        while !stack.is_empty() {
            let curr_pair = stack.pop().unwrap();
            let visited = curr_pair.1;
            if let Some(node) = curr_pair.0.clone() {
                let node = node.borrow();

                if visited {
                    ans.push(node.val);
                } else {
                    stack.push((curr_pair.0, true));

                    if node.right != None {
                        stack.push((node.right.clone(), false));
                    }

                    if node.left != None {
                        stack.push((node.left.clone(), false));
                    }
                }
                
            }
        }

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

2.4 层次遍历

利用队列实现二叉树的层次遍历。

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        let mut ans: Vec<Vec<i32>> = vec![];
        use std::collections::VecDeque;
        let mut queue: VecDeque<Option<Rc<RefCell<TreeNode>>>> = VecDeque::new();
        if root != None {
            queue.push_back(root);
        }
        
        while !queue.is_empty() {
            let mut curr_level: Vec<i32> = vec![];
            for _ in 0..queue.len() {
                if let Some(node) = queue.pop_front().unwrap() {
                    let node = node.borrow();
                    curr_level.push(node.val);
                    if node.left != None {
                        queue.push_back(node.left.clone());
                    }
                    if node.right != None {
                        queue.push_back(node.right.clone());
                    }
                }
            }
            ans.push(curr_level);
        }

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

---

3. DFS

3.1 前序遍历

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut ans = vec![];
        fn dfs(node: Option<Rc<RefCell<TreeNode>>>, arr: &mut Vec<i32>) {
            match node {
                Some(node) => {
                    let node = node.borrow();
                    arr.push(node.val);
                    dfs(node.left.clone(), arr);
                    dfs(node.right.clone(), arr);
                },
                None => return,
            }
        }
        dfs(root, &mut ans);
        ans
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.2 中序遍历

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut ans: Vec<i32> = vec![];

        fn dfs(node: Option<Rc<RefCell<TreeNode>>>, arr: &mut Vec<i32>) {
            match node {
                Some(node) => {
                    let node = node.borrow();
                    dfs(node.left.clone(), arr);
                    arr.push(node.val);
                    dfs(node.right.clone(), arr);
                },
                Node => return,
            }
        }

        dfs(root, &mut ans);

        ans
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.2 后序遍历

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut ans: Vec<i32> = vec![];

        fn dfs(node: Option<Rc<RefCell<TreeNode>>>, arr: &mut Vec<i32>) {
            match node {
                Some(node) => {
                    let node = node.borrow();
                    dfs(node.left.clone(), arr);
                    dfs(node.right.clone(), arr);
                    arr.push(node.val);
                },
                Node => {
                    return;
                },
            }
        }

        dfs(root, &mut ans);

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