php 解法, 执行用时: 147 ms, 内存消耗: 52.5 MB, 提交时间: 2024-02-23 11:21:56

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @param Integer $k
     * @return Integer
     */
    function kthLargestLevelSum($root, $k) {
        $q = [$root];
        $sum = [];
        while ( $q ) {
            $tmp = $q;
            $s = 0;
            $q = [];
            foreach ( $tmp as $node ) {
                $s += $node->val;
                if ( $node->left ) $q[] = $node->left;
                if ( $node->right ) $q[] = $node->right;
            }
            $sum[] = $s;
        }
        $n = count($sum);
        if ( $n < $k ) return -1;
        sort($sum);
        return $sum[$n-$k];
    }
}

java 解法, 执行用时: 41 ms, 内存消耗: 66.6 MB, 提交时间: 2024-02-23 11:17:03

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public long kthLargestLevelSum(TreeNode root, int k) {
        List<Long> a = new ArrayList<>();
        List<TreeNode> q = List.of(root);
        while (!q.isEmpty()) {
            long sum = 0;
            List<TreeNode> tmp = q;
            q = new ArrayList<>();
            for (TreeNode node : tmp) {
                sum += node.val;
                if (node.left != null)  q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            a.add(sum);
        }
        int n = a.size();
        if (k > n) {
            return -1;
        }
        Collections.sort(a);
        return a.get(n - k);
    }
}

rust 解法, 执行用时: 35 ms, 内存消耗: 11.5 MB, 提交时间: 2024-02-23 11:16:37

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn kth_largest_level_sum(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i64 {
        let mut a = Vec::new();
        let mut cur = vec![root.unwrap()];
        while !cur.is_empty() {
            let mut sum = 0i64;
            let mut nxt = Vec::new();
            for node in cur {
                let mut x = node.borrow_mut();
                sum += x.val as i64;
                if let Some(left) = x.left.take() {
                    nxt.push(left);
                }
                if let Some(right) = x.right.take() {
                    nxt.push(right);
                }
            }
            cur = nxt;
            a.push(sum);
        }
        let k = k as usize;
        if k > a.len() {
            return -1;
        }
        a.sort_unstable();
        a[a.len() - k]
    }
}

javascript 解法, 执行用时: 336 ms, 内存消耗: 94.7 MB, 提交时间: 2024-02-23 11:16:14

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargestLevelSum = function(root, k) {
    const a = [];
    let q = [root];
    while (q.length) {
        let sum = 0;
        const tmp = q;
        q = [];
        for (const node of tmp) {
            sum += node.val;
            if (node.left)  q.push(node.left);
            if (node.right) q.push(node.right);
        }
        a.push(sum);
    }
    if (k > a.length) {
        return -1;
    }
    a.sort((a, b) => b - a);
    return a[k - 1];
};

golang 解法, 执行用时: 224 ms, 内存消耗: 20.8 MB, 提交时间: 2023-03-09 14:24:42

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthLargestLevelSum(root *TreeNode, k int) int64 {
	q := []*TreeNode{root}
	sum := []int{}
	for len(q) > 0 {
		tmp, s := q, 0
		q = nil
		for _, node := range tmp {
			s += node.Val
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
		sum = append(sum, s)
	}
	n := len(sum)
	if n < k {
		return -1
	}
	sort.Ints(sum) // 也可以用快速选择
	return int64(sum[n-k])
}

python3 解法, 执行用时: 520 ms, 内存消耗: 59.7 MB, 提交时间: 2023-03-09 14:24:00

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
# bfs遍历，
class Solution:
    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
        q = [root]
        sum = []
        while q:
            tmp, s = q, 0
            q = []
            for node in tmp:
                s += node.val
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            sum.append(s)
        sum.sort()  # 也可以用快速选择
        return -1 if len(sum) < k else sum[-k]