首页 > 其他 > 详细

Second largest node in the BST

时间:2019-07-30 14:46:29      阅读:165      评论:0      收藏:0      [点我收藏+]

Find the second largest node in the BST

分析:

如果root有右节点,很明显第二大的node有可能在右子树里。唯一不满足的条件就是右子树只有一个node. 这个时候root就是第二大node. 所以我们需要把root(可能是第二大node)也传下去。

如果root没有右节点,我们只要找左子树的最大node就可以了。

 1 public class Solution {
 2     public Node secondLargest(Node root) {
 3         return helper(root, null);
 4     }
 5     
 6     private Node helper(Node root, Node previous) {
 7         if (root.right != null) {
 8             return helper(root.right, root);
 9         }
10         
11         if (root.left != null) {
12             return rightMost(root.left);
13         }
14         
15         return previous;
16     }
17     
18     private Node rightMost(Node node) {
19         while (node.right != null) {
20             node = node.right;
21         }
22         return node;
23     }
24

 

Second largest node in the BST

原文:https://www.cnblogs.com/beiyeqingteng/p/11269463.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!