Re: [閒聊] 每日LeetCode

[yam276 (史萊哲林的優等生)]

※ 引述《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;
    }
};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1689326522.A.E10.html