leetcode简朴题20 N.101 对称二叉树 rust形貌

 

1. // [1,2,2,3,4,4,3] true
2. // [1,2,2,null,3,null,3] false
3. use std::rc::Rc;
4. use std::cell::RefCell;
5. #[derive(Debug, PartialEq, Eq)]
6. pub struct TreeNode {
7.   pub val: i32,
8.   pub left: Option<Rc<RefCell<TreeNode>>>,
9.   pub right: Option<Rc<RefCell<TreeNode>>>,
10. }
11. impl TreeNode {
12.   #[inline]
13.   pub fn new(val: i32) -> Self {
14.     TreeNode {
15.       val,
16.       left: None,
17.       right: None
18.     }
19.   }
20. }
21. // 递归
22. pub fn is_symmetric(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
23.     is_mirror(&root, &root)
24. }
25. // 递归的辅助函数，
26. fn is_mirror(
27.     left: &Option<Rc<RefCell<TreeNode>>>,
28.     right: &Option<Rc<RefCell<TreeNode>>>,
29. ) -> bool {
30.     match (left, right) {
31.         (Some(left_node), Some(right_node)) => {
32.             let left_node = left_node.borrow();
33.             let right_node = right_node.borrow();
34.             left_node.val == right_node.val
35.                 && is_mirror(&left_node.left, &right_node.right)
36.                 && is_mirror(&left_node.right, &right_node.left)
37.         }
38.         (None, None) => true,
39.         _ => false,
40.     }
41. }
42. use std::collections::VecDeque;
43. // 迭代
44. pub fn is_symmetric2(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
45.     if root.is_none() {
46.         return true;
47.     }
49.     let mut queue = VecDeque::new();
50.     queue.push_back(root.clone());
51.     queue.push_back(root.clone());
53.     while !queue.is_empty() {
54.         let left = queue.pop_front().unwrap();
55.         let right = queue.pop_front().unwrap();
57.         if left.is_none() && right.is_none() {
58.             continue;
59.         }
61.         if left.is_none() || right.is_none() {
62.             return false;
63.         }
65.         let left_node = left.as_ref().unwrap().borrow();
66.         let right_node = right.as_ref().unwrap().borrow();
68.         if left_node.val != right_node.val {
69.             return false;
70.         }
72.         queue.push_back(left_node.left.clone());
73.         queue.push_back(right_node.right.clone());
74.         queue.push_back(left_node.right.clone());
75.         queue.push_back(right_node.left.clone());
76.     }
78.     true
79. }
80. fn main() {
81.     // 根据 [1,2,2,3,4,4,3] true 编写测试用例
82.     let tree = Some(Rc::new(RefCell::new(TreeNode {
83.         val:1,
84.         left:Some(Rc::new(RefCell::new(TreeNode {
85.             val:2,
86.             left:Some(Rc::new(RefCell::new(TreeNode {
87.                 val:3,
88.                 left:None,
89.                 right:None,
90.             }))),
91.             right:Some(Rc::new(RefCell::new(TreeNode {
92.                 val:4,
93.                 left:None,
94.                 right:None,
95.             }))),
96.         }))),
97.         right:Some(Rc::new(RefCell::new(TreeNode {
98.             val:2,
99.             left:Some(Rc::new(RefCell::new(TreeNode {
100.                 val:4,
101.                 left:None,
102.                 right:None,
103.             }))),
104.             right:Some(Rc::new(RefCell::new(TreeNode {
105.                 val:3,
106.                 left:None,
107.                 right:None,
108.             }))),
109.         }))),
110.     })));
111.     assert_eq!(is_symmetric(tree.clone()), true);
112.     assert_eq!(is_symmetric2(tree.clone()), true);
113. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。