Steven's Blog

Appearance

On this page

每天一道Rust-LeetCode(2019-10-10) ​

坚持每天一道题,刷题学习Rust.

题目描述 ​

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 : 给定二叉树

          1
         / \
        2   3
       /  \
      4    5
     /      \
    0        6
              \
               7
                \
                 8

返回 3, 它的长度是路径 [0,4,2,5,6,7,8] 或者 [3,1,2,5,6,7,8]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/diameter-of-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路 ​

上一种方法是看错题目了,理解成普通二叉树了, 如果是bst,可以进行简化

  1. 百度了一下,BST要求没有相等的节点,那么就简化了很多
  2. 采用先右子树遍历,然后不断累加更新即可

解题过程 ​

rust
use crate::share::TreeNode;
use std::cell::RefCell;
use std::cmp::max;
use std::rc::Rc;

struct Solution {}
impl Solution {
    pub fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let (mut h, _) = Self::internal(root);
        //刚刚算的是节点数,要减去1,还要考虑到树是空的情况,避免出现负值
        if h >= 1 {
            h -= 1;
        }
        return h;
    }
    /*
    第一个: 经过自身(或者不经过自身)截至的最大节点数
    第二个: 可以继续走下去的最大节点数
    */
    fn internal(root: Option<Rc<RefCell<TreeNode>>>) -> (i32, i32) {
        if root.is_none() {
            return (0, 0);
        }
        let r = root.unwrap();
        let (l1, l2) = Self::internal(r.borrow().left.clone());
        let (r1, r2) = Self::internal(r.borrow().right.clone());
        let mut c2 = max(l2, r2) + 1;
        let mut c1 = l2 + r2 + 1;
        c1 = max(c1, l1);
        c1 = max(c1, r1);
        println!("node={},ret={:?}", r.borrow().val, (c1, c2));
        return (c1, c2);
    }
}
#[cfg(test)]
mod test {
    use super::*;
    use crate::share::*;
    #[test]
    fn test_level_order_bottom() {
        //        assert_eq!(
        //            Solution::diameter_of_binary_tree(build_tree(&vec![1, 2, 3, 4, 5])),
        //            3
        //        );
        //        assert_eq!(
        //            Solution::diameter_of_binary_tree(build_tree(&vec![2, 1, 3])),
        //            2
        //        );
        let t = build_tree_ignore_parent(&vec![
            4, -7, -3, null, null, -9, -3, 9, -7, -4, null, 6, null, -6, -6, null, null, 0, 6, 5,
            null, 9, null, null, -1, -4, null, null, null, -2,
        ]);
        println!("t={:?}", t);
        assert_eq!(Solution::diameter_of_binary_tree(t), 8);
    }
}

一点感悟 ​

其他 ​

欢迎关注我的github,本项目文章所有代码都可以找到.