国产av日韩一区二区三区精品,成人性爱视频在线观看,国产,欧美,日韩,一区,www.成色av久久成人,2222eeee成人天堂

Home Backend Development PHP Tutorial Kth Largest Sum in a Binary Tree

Kth Largest Sum in a Binary Tree

Oct 23, 2024 am 06:16 AM

2583. Kth Largest Sum in a Binary Tree

Difficulty: Medium

Topics: Tree, Breadth-First Search, Sorting, Binary Tree

You are given the root of a binary tree and a positive integer k.

The level sum in the tree is the sum of the values of the nodes that are on the same level.

Return the kth largest level sum in the tree (not necessarily distinct). If there are fewer than k levels in the tree, return -1.

Note that two nodes are on the same level if they have the same distance from the root.

Example 1:

Kth Largest Sum in a Binary Tree

  • Input: root = [5,8,9,2,1,3,7,4,6], k = 2
  • Output: 13
  • Explanation: The level sums are the following:
    • Level 1: 5.
    • Level 2: 8 9 = 17.
    • Level 3: 2 1 3 7 = 13.
    • Level 4: 4 6 = 10.
    • The 2nd largest level sum is 13.

Example 2:

Kth Largest Sum in a Binary Tree

  • Input: root = [1,2,null,3], k = 1
  • Output: 3
  • Explanation: The largest level sum is 3.

Constraints:

  • The number of nodes in the tree is n.
  • 2 <= n <= 105
  • 1 <= Node.val <= 106
  • 1 <= k <= n

Hint:

  1. Find the sum of values of nodes on each level and return the kth largest one.
  2. To find the sum of the values of nodes on each level, you can use a DFS or BFS algorithm to traverse the tree and keep track of the level of each node.

Solution:

We'll follow these steps:

  1. Level Order Traversal: We will use a Breadth-First Search (BFS) to traverse the tree level by level.
  2. Calculate Level Sums: During the BFS traversal, we'll calculate the sum of node values at each level.
  3. Sort and Find k-th Largest Sum: After calculating the sums for all levels, we'll sort the sums and retrieve the k-th largest value.

Let's implement this solution in PHP: 2583. Kth Largest Sum in a Binary Tree

val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

/**
 * @param TreeNode $root
 * @param Integer $k
 * @return Integer
 */
function kthLargestLevelSum($root, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1:
// Input: root = [5,8,9,2,1,3,7,4,6], k = 2
$root1 = new TreeNode(5);
$root1->left = new TreeNode(8);
$root1->right = new TreeNode(9);
$root1->left->left = new TreeNode(2);
$root1->left->right = new TreeNode(1);
$root1->right->left = new TreeNode(3);
$root1->right->right = new TreeNode(7);
$root1->left->left->left = new TreeNode(4);
$root1->left->left->right = new TreeNode(6);
echo kthLargestLevelSum($root1, 2); // Output: 13

// Example 2:
// Input: root = [1,2,null,3], k = 1
$root2 = new TreeNode(1);
$root2->left = new TreeNode(2);
$root2->left->left = new TreeNode(3);
echo kthLargestLevelSum($root2, 1); // Output: 3
?>




Explanation:

  1. TreeNode Class: We define the TreeNode class to represent a node in the binary tree, where each node has a value (val), a left child (left), and a right child (right).

  2. BFS Traversal: The function kthLargestLevelSum uses a queue to perform a BFS traversal. For each level, we sum the values of the nodes and store the result in an array ($levelSums).

  3. Sorting Level Sums: After traversing the entire tree and calculating the level sums, we sort the sums in descending order using rsort. This allows us to easily access the k-th largest sum.

  4. Edge Case Handling: If there are fewer than k levels, we return -1.

Time Complexity:

  • BFS Traversal: O(n), where n is the number of nodes in the tree.
  • Sorting: O(m log m), where m is the number of levels in the tree. Since m is much smaller than n, sorting is relatively fast.
  • Overall time complexity: O(n m log m).

Space Complexity:

  • Queue: O(n), for storing nodes during BFS.
  • Level Sums: O(m), for storing the sum of each level.
  • Overall space complexity: O(n).

This approach ensures that we traverse the tree efficiently and return the correct kth largest level sum.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

  • LinkedIn
  • GitHub

The above is the detailed content of Kth Largest Sum in a Binary Tree. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undress AI Tool

Undress AI Tool

Undress images for free

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

How to set PHP time zone? How to set PHP time zone? Jun 25, 2025 am 01:00 AM

TosettherighttimezoneinPHP,usedate_default_timezone_set()functionatthestartofyourscriptwithavalididentifiersuchas'America/New_York'.1.Usedate_default_timezone_set()beforeanydate/timefunctions.2.Alternatively,configurethephp.inifilebysettingdate.timez

How to quickly test PHP code snippets? How to quickly test PHP code snippets? Jun 25, 2025 am 12:58 AM

ToquicklytestaPHPcodesnippet,useanonlinePHPsandboxlike3v4l.orgorPHPize.onlineforinstantexecutionwithoutsetup;runcodelocallywithPHPCLIbycreatinga.phpfileandexecutingitviatheterminal;optionallyusephp-rforone-liners;setupalocaldevelopmentenvironmentwith

How to upgrade PHP version? How to upgrade PHP version? Jun 27, 2025 am 02:14 AM

Upgrading the PHP version is actually not difficult, but the key lies in the operation steps and precautions. The following are the specific methods: 1. Confirm the current PHP version and running environment, use the command line or phpinfo.php file to view; 2. Select the suitable new version and install it. It is recommended to install it with 8.2 or 8.1. Linux users use package manager, and macOS users use Homebrew; 3. Migrate configuration files and extensions, update php.ini and install necessary extensions; 4. Test whether the website is running normally, check the error log to ensure that there is no compatibility problem. Follow these steps and you can successfully complete the upgrade in most situations.

Steps to configure a PHP development environment on Linux Steps to configure a PHP development environment on Linux Jun 30, 2025 am 01:57 AM

TosetupaPHPdevelopmentenvironmentonLinux,installPHPandrequiredextensions,setupawebserverlikeApacheorNginx,testwithaPHPfile,andoptionallyinstallMySQLandComposer.1.InstallPHPandextensionsviapackagemanager(e.g.,sudoaptinstallphpphp-mysqlphp-curlphp-mbst

PHP beginner guide: Detailed explanation of local environment configuration PHP beginner guide: Detailed explanation of local environment configuration Jun 27, 2025 am 02:09 AM

To set up a PHP development environment, you need to select the appropriate tools and install the configuration correctly. ①The most basic PHP local environment requires three components: the web server (Apache or Nginx), the PHP itself and the database (such as MySQL/MariaDB); ② It is recommended that beginners use integration packages such as XAMPP or MAMP, which simplify the installation process. XAMPP is suitable for Windows and macOS. After installation, the project files are placed in the htdocs directory and accessed through localhost; ③MAMP is suitable for Mac users and supports convenient switching of PHP versions, but the free version has limited functions; ④ Advanced users can manually install them by Homebrew, in macOS/Linux systems

How to combine two php arrays unique values? How to combine two php arrays unique values? Jul 02, 2025 pm 05:18 PM

To merge two PHP arrays and keep unique values, there are two main methods. 1. For index arrays or only deduplication, use array_merge and array_unique combinations: first merge array_merge($array1,$array2) and then use array_unique() to deduplicate them to finally get a new array containing all unique values; 2. For associative arrays and want to retain key-value pairs in the first array, use the operator: $result=$array1 $array2, which will ensure that the keys in the first array will not be overwritten by the second array. These two methods are applicable to different scenarios, depending on whether the key name is retained or only the focus is on

How do I prevent cross-site request forgery (CSRF) attacks in PHP? How do I prevent cross-site request forgery (CSRF) attacks in PHP? Jun 28, 2025 am 02:25 AM

TopreventCSRFattacksinPHP,implementanti-CSRFtokens.1)Generateandstoresecuretokensusingrandom_bytes()orbin2hex(random_bytes(32)),savethemin$_SESSION,andincludetheminformsashiddeninputs.2)ValidatetokensonsubmissionbystrictlycomparingthePOSTtokenwiththe

php regex for password strength php regex for password strength Jul 03, 2025 am 10:33 AM

To determine the strength of the password, it is necessary to combine regular and logical processing. The basic requirements include: 1. The length is no less than 8 digits; 2. At least containing lowercase letters, uppercase letters, and numbers; 3. Special character restrictions can be added; in terms of advanced aspects, continuous duplication of characters and incremental/decreasing sequences need to be avoided, which requires PHP function detection; at the same time, blacklists should be introduced to filter common weak passwords such as password and 123456; finally it is recommended to combine the zxcvbn library to improve the evaluation accuracy.

See all articles