※ 引述《yam276 (史莱哲林的优等生)》之铭言：
: 用Easy来玩Rust
110. Balanced Binary Tree
Given a binary tree, determine if it is height-balanced
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Example 3:
Input: root = []
Output: true
Constraints:
The number of nodes in the tree is in the range [0, 5000].
-10^4 <= Node.val <= 10^4
直接用上一题的东西来用
不修改MaxDepth的内容
Code:
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn is_balanced(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
match root {
None => return true,
Some(node) => {
let mut node = node.borrow_mut();
let left_depth = Self::max_depth(node.left.clone());
let right_depth = Self::max_depth(node.right.clone());
if (left_depth - right_depth).abs() > 1 {
return false;
}
return Self::is_balanced(node.left.clone())
&& Self::is_balanced(node.right.clone());
}
}
}
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
match root {
Some(node) => {
let mut node = node.borrow_mut();
let left_depth = Self::max_depth(node.left.clone());
let right_depth = Self::max_depth(node.right.clone());
return std::cmp::max(left_depth, right_depth) + 1;
}
None => return 0,
}
return 0;
}
}
等价于：
class Solution {
public:
bool isBalanced(TreeNode* root) {
if (!root)
return true;
int left_depth = MaxDepth(root->left);
int right_depth = MaxDepth(root->right);
if (abs(left_depth - right_depth) > 1)
return false;
return isBalanced(root->left) && isBalanced(root->right);
}
int MaxDepth(TreeNode* root)
{
if (root == nullptr)
return 0;
int left_depth = MaxDepth(root->left);
int right_depth = MaxDepth(root->right);
return max(left_depth, right_depth) + 1;
}
};