1302.层数最深叶子节点的和

链接：1302.层数最深叶子节点的和
难度：Medium
标签：树、深度优先搜索、广度优先搜索、二叉树
简介：给你一棵二叉树的根节点 root ，请你返回 层数最深的叶子节点的和 。

题解 1 - typescript

• 编辑时间：2021-05-13
• 执行用时：124ms
• 内存消耗：48.3MB
• 编程语言：typescript
• 解法介绍：层序遍历。

function deepestLeavesSum(root: TreeNode | null): number {
  if (root === null) return 0;
  const queue: TreeNode[] = [root];
  let size = 1;
  let ans = root.val;
  while (queue.length !== 0) {
    const node = queue.shift()!;
    node.left && queue.push(node.left);
    node.right && queue.push(node.right);
    if (--size === 0) {
      if (queue.length !== 0) ans = queue.reduce((total, node) => total + node.val, 0);
      size = queue.length;
    }
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-05-13
• 执行用时：116ms
• 内存消耗：48.3MB
• 编程语言：typescript
• 解法介绍：中序遍历。

function deepestLeavesSum(root: TreeNode | null): number {
  if (root === null) return 0;
  let maxDep = 1;
  let ans = root.val;
  const inorder = (node: TreeNode, dep = 1): void => {
    if (dep > maxDep) {
      ans = 0;
      maxDep = dep;
    }
    node.left && inorder(node.left, dep + 1);
    node.right && inorder(node.right, dep + 1);
    if (!node.left && !node.right && dep === maxDep) ans += node.val;
  };
  inorder(root);
  return ans;
}

题解 3 - rust

• 编辑时间：2022-08-17
• 执行用时：12ms
• 内存消耗：3MB
• 编程语言：rust
• 解法介绍：层序遍历。

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
    pub fn deepest_leaves_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let root = root.unwrap();
        let mut q = VecDeque::<Rc<RefCell<TreeNode>>>::new();
        q.push_back(root.clone());
        let mut ans = root.as_ref().borrow().val;
        let mut cur = 0;
        let mut size = 1;
        while !q.is_empty() {
            let node = q.pop_front().unwrap();
            let node = node.as_ref().borrow();
            if node.left.is_some() {
                cur += node.left.as_ref().unwrap().as_ref().borrow().val;
                q.push_back(node.left.as_ref().unwrap().clone());
            }
            if node.right.is_some() {
                cur += node.right.as_ref().unwrap().as_ref().borrow().val;
                q.push_back(node.right.as_ref().unwrap().clone());
            }
            size -= 1;
            if size == 0 {
                size = q.len();
                if size != 0 {
                    ans = cur;
                }
                cur = 0;
            }
        }
        ans
    }
}