第587题-打印二叉树的所有可能路径

问题描述

二叉树示例

这道题很简单，要求给定一颗二叉树，返回所有可能的路径，思路就是深度优先搜索，考察的是基本功，看起来没什么trick

rust语言实现

use std::cell::RefCell;
use std::fmt::Debug;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode<T: Ord + Debug + Clone> {
    pub elem: T,
    pub left: Link<T>,
    pub right: Link<T>,
}

type Link<T> = Option<Rc<RefCell<TreeNode<T>>>>;

impl<T: Ord + Debug + Clone> TreeNode<T> {
    pub fn new(t: T) -> Self {
        TreeNode {
            elem: t,
            left: None,
            right: None,
        }
    }

    pub fn dfs_helper(
        root: Option<&Rc<RefCell<TreeNode<T>>>>,
        mut cur: Vec<T>,
        res: &mut Vec<Vec<T>>,
    ) {
        if let Some(root_node) = root {
            cur.push(root_node.borrow().elem.clone());
            if root_node.borrow().left.is_none() && root_node.borrow().right.is_none() {
                res.push(cur); // reached the end, stop recursive
            } else {
                Self::dfs_helper(root_node.borrow().left.as_ref(), cur.clone(), res);
                Self::dfs_helper(root_node.borrow().right.as_ref(), cur, res);
            }
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_dfs() {
        let mut n1 = TreeNode::new(1);
        let n2 = TreeNode::new(2);
        let mut n3 = TreeNode::new(3);
        let n4 = TreeNode::new(4);
        let n5 = TreeNode::new(5);

        n3.left = Some(Rc::new(RefCell::new(n4)));
        n3.right = Some(Rc::new(RefCell::new(n5)));

        n1.left = Some(Rc::new(RefCell::new(n2)));
        n1.right = Some(Rc::new(RefCell::new(n3)));

        let mut res: Vec<Vec<i32>> = vec![];
        TreeNode::dfs_helper(Some(&Rc::new(RefCell::new(n1))), vec![], &mut res);

        assert_eq!(vec![vec![1, 2], vec![1, 3, 4], vec![1, 3, 5]], res);
    }
}

代码不难，最多的地方应该是在构造这棵二叉树上，因为不是二叉搜索树，所以构造起来稍微复杂点。构造完了之后就用深度优先搜索去遍历，深搜是一个递归算法，具体思路是如果当前节点是叶子节点，则递归终止，如果有左子树，则递归搜索左子树，如果有右子树则递归搜索右子树