rustgym/leetcode/
_257_binary_tree_paths.rs

1struct Solution;
2use rustgym_util::*;
3
4struct Path {
5    stack: Vec<i32>,
6}
7
8impl ToString for Path {
9    fn to_string(&self) -> String {
10        let s: Vec<String> = self.stack.iter().map(|x| x.to_string()).collect();
11        s.join("->")
12    }
13}
14
15trait Preorder {
16    fn preorder(&self, path: &mut Path, v: &mut Vec<String>);
17}
18
19impl Preorder for TreeLink {
20    fn preorder(&self, path: &mut Path, v: &mut Vec<String>) {
21        if let Some(node) = self {
22            let node = node.borrow();
23            path.stack.push(node.val);
24            if node.left.is_none() && node.right.is_none() {
25                v.push(path.to_string());
26            }
27            if node.left.is_some() {
28                node.left.preorder(path, v);
29            }
30            if node.right.is_some() {
31                node.right.preorder(path, v);
32            }
33            path.stack.pop();
34        }
35    }
36}
37
38impl Solution {
39    fn binary_tree_paths(root: TreeLink) -> Vec<String> {
40        let mut path = Path { stack: vec![] };
41        let mut res = vec![];
42        root.preorder(&mut path, &mut res);
43        res
44    }
45}
46
47#[test]
48fn test() {
49    let root = tree!(1, tree!(2, None, tree!(5)), tree!(3));
50    let paths: Vec<String> = vec_string!["1->2->5", "1->3"];
51    assert_eq!(Solution::binary_tree_paths(root), paths);
52}
rustgym/leetcode/_257_binary_tree_paths.rs

rustgym/leetcode/
_257_binary_tree_paths.rs
