0


leetcode简单题23 N.110 平衡二叉树 rust描述

  1. // [3,9,20,null,null,15,7] true
  2. // [1,2,2,3,3,null,null,4,4] false
  3. // [] true
  4. // Definition for a binary tree node.
  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. use std::rc::Rc;
  22. use std::cell::RefCell;
  23. pub fn is_balanced(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
  24. // Helper function to determine height and if the subtree is balanced
  25. fn check_height_and_balance(node: &Option<Rc<RefCell<TreeNode>>>) -> (bool, i32) {
  26. if let Some(node) = node {
  27. let left = check_height_and_balance(&node.borrow().left);
  28. let right = check_height_and_balance(&node.borrow().right);
  29. let is_balanced = left.0 && right.0 && (left.1 - right.1).abs() <= 1;
  30. let height = 1 + left.1.max(right.1);
  31. (is_balanced, height)
  32. } else {
  33. (true, 0)
  34. }
  35. }
  36. check_height_and_balance(&root).0
  37. }
  38. fn build_tree(values: Vec<Option<i32>>) -> Option<Rc<RefCell<TreeNode>>> {
  39. if values.is_empty() {
  40. return None;
  41. }
  42. let root = Rc::new(RefCell::new(TreeNode::new(values[0].unwrap())));
  43. let mut queue = vec![Rc::clone(&root)];
  44. let mut i = 1;
  45. while i < values.len() {
  46. let current = queue.remove(0);
  47. if let Some(val) = values[i] {
  48. let left_node = Rc::new(RefCell::new(TreeNode::new(val)));
  49. current.borrow_mut().left = Some(Rc::clone(&left_node));
  50. queue.push(left_node);
  51. }
  52. i += 1;
  53. if i < values.len() {
  54. if let Some(val) = values[i] {
  55. let right_node = Rc::new(RefCell::new(TreeNode::new(val)));
  56. current.borrow_mut().right = Some(Rc::clone(&right_node));
  57. queue.push(right_node);
  58. }
  59. i += 1;
  60. }
  61. }
  62. Some(root)
  63. }
  64. fn main() {
  65. let tree = build_tree(vec![Some(3), Some(9), Some(20), None, None, Some(15), Some(7)]);
  66. assert_eq!(is_balanced(tree), true);
  67. let tree = build_tree(vec![Some(1), Some(2), Some(2), Some(3), Some(3), None, None, Some(4), Some(4)]);
  68. assert_eq!(is_balanced(tree), false);
  69. let tree = build_tree(vec![]);
  70. assert_eq!(is_balanced(tree), true);
  71. }
标签: leetcode rust 算法

本文转载自: https://blog.csdn.net/BECOMEviolet/article/details/140408644
版权归原作者 独好紫罗兰 所有, 如有侵权,请联系我们删除。

“leetcode简单题23 N.110 平衡二叉树 rust描述”的评论:

还没有评论