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:
- 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:
- 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:
- Find the sum of values of nodes on each level and return the kth largest one.
- 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:
- Level Order Traversal: We will use a Breadth-First Search (BFS) to traverse the tree level by level.
- Calculate Level Sums: During the BFS traversal, we'll calculate the sum of node values at each level.
- 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:
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).
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).
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.
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:
- 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!

Hot AI Tools

Undress AI Tool
Undress images for free

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Clothoff.io
AI clothes remover

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

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

TostaycurrentwithPHPdevelopmentsandbestpractices,followkeynewssourceslikePHP.netandPHPWeekly,engagewithcommunitiesonforumsandconferences,keeptoolingupdatedandgraduallyadoptnewfeatures,andreadorcontributetoopensourceprojects.First,followreliablesource

PHPbecamepopularforwebdevelopmentduetoitseaseoflearning,seamlessintegrationwithHTML,widespreadhostingsupport,andalargeecosystemincludingframeworkslikeLaravelandCMSplatformslikeWordPress.Itexcelsinhandlingformsubmissions,managingusersessions,interacti

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

The key to writing clean and easy-to-maintain PHP code lies in clear naming, following standards, reasonable structure, making good use of comments and testability. 1. Use clear variables, functions and class names, such as $userData and calculateTotalPrice(); 2. Follow the PSR-12 standard unified code style; 3. Split the code structure according to responsibilities, and organize it using MVC or Laravel-style catalogs; 4. Avoid noodles-style code and split the logic into small functions with a single responsibility; 5. Add comments at key points and write interface documents to clarify parameters, return values ??and exceptions; 6. Improve testability, adopt dependency injection, reduce global state and static methods. These practices improve code quality, collaboration efficiency and post-maintenance ease.

Yes,youcanrunSQLqueriesusingPHP,andtheprocessinvolveschoosingadatabaseextension,connectingtothedatabase,executingqueriessafely,andclosingconnectionswhendone.Todothis,firstchoosebetweenMySQLiorPDO,withPDObeingmoreflexibleduetosupportingmultipledatabas

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

PHP page caching improves website performance by reducing server load and speeding up page loading. 1. Basic file cache avoids repeated generation of dynamic content by generating static HTML files and providing services during the validity period; 2. Enable OPcache to compile PHP scripts into bytecode and store them in memory, improving execution efficiency; 3. For dynamic pages with parameters, they should be cached separately according to URL parameters, and avoid cached user-specific content; 4. Lightweight cache libraries such as PHPFastCache can be used to simplify development and support multiple storage drivers. Combining these methods can effectively optimize the caching strategy of PHP projects.

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.
