110. Balanced Binary Tree Easy

1/**
2 * [110] Balanced Binary Tree
3 *
4 * Given a binary tree, determine if it is height-balanced.
5 * For this problem, a height-balanced binary tree is defined as:
6 * <blockquote>
7 * a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
8 * </blockquote>
9 *  
10 * Example 1:
11 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/06/balance_1.jpg" style="width: 342px; height: 221px;" />
12 * Input: root = [3,9,20,null,null,15,7]
13 * Output: true
14 * 
15 * Example 2:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/06/balance_2.jpg" style="width: 452px; height: 301px;" />
17 * Input: root = [1,2,2,3,3,null,null,4,4]
18 * Output: false
19 * 
20 * Example 3:
21 * 
22 * Input: root = []
23 * Output: true
24 * 
25 *  
26 * Constraints:
27 * 
28 * The number of nodes in the tree is in the range [0, 5000].
29 * -10^4 <= Node.val <= 10^4
30 * 
31 */
32pub struct Solution {}
33#[allow(unused_imports)]
34use crate::util::tree::{TreeNode, to_tree};
35
36// problem: https://leetcode.com/problems/balanced-binary-tree/
37// discuss: https://leetcode.com/problems/balanced-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41// Definition for a binary tree node.
42// #[derive(Debug, PartialEq, Eq)]
43// pub struct TreeNode {
44//   pub val: i32,
45//   pub left: Option<Rc<RefCell<TreeNode>>>,
46//   pub right: Option<Rc<RefCell<TreeNode>>>,
47// }
48// 
49// impl TreeNode {
50//   #[inline]
51//   pub fn new(val: i32) -> Self {
52//     TreeNode {
53//       val,
54//       left: None,
55//       right: None
56//     }
57//   }
58// }
59use std::rc::Rc;
60use std::cell::RefCell;
61use std::cmp;
62impl Solution {
63    pub fn is_balanced(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
64        Self::check_balance(root).0
65    }
66
67    fn check_balance(root: Option<Rc<RefCell<TreeNode>>>) -> (bool, i32) {
68        match root {
69            Some(r) => {
70                let right = Self::check_balance(r.borrow().right.clone());
71                let left = Self::check_balance(r.borrow().left.clone());
72                (right.0 && left.0 && (right.1 - left.1).abs() <= 1, cmp::max(right.1, left.1) + 1)
73            },
74            None => (true, 0)
75        }
76    }
77}
78
79// submission codes end
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84    use crate::tree;
85
86    #[test]
87    fn test_110() {
88        assert_eq!(Solution::is_balanced(tree![3,9,20,null,null,15,7]), true);
89        assert_eq!(Solution::is_balanced(tree![1,2,2,3,3,null,null,4,4]), false);
90    }
91}
92