Это вопрос интервью. Найдите второй макс в BST.
Максимальный элемент - самый правый лист в BST. Второй макс является либо его родителем, либо его левым дочерним элементом. Таким образом, решение состоит в том, чтобы пересечь BST, чтобы найти самый правый лист и проверить его родительский и левый ребенок.
Имеет ли смысл?
Напомним, что вы можете перечислить узлы BST в обратном порядке, выполнив измененный обход посторонних], в котором вы сначала исследуете правильное поддерево. Это приводит к простому алгоритму:
Node rightmost = findRightmostNode(root)
if (rightmost.left != null) {
return findRightmostNode(rightmost.left)
else{
return rightmost.parent
}
Он возвращает null, если дерево имеет только один элемент.
Нет, это неправильно. Рассмотрим этот BST:
137
/
42
\
99
Здесь значение "второе-максимальное" является самым правым дочерним элементом левого дочернего элемента максимального значения. Ваш алгоритм необходимо будет обновить, чтобы вы проверили родительское значение максимального значения или самый правый нижний дочерний элемент левого дочернего элемента max.
Также обратите внимание, что max не обязательно является самым правым листом node, а node в нижней части правого позвоночника дерева. Выше 137 не является листом.
Надеюсь, это поможет!
public static int findSecondLargestValueInBST(Node root)
{
int secondMax;
Node pre = root;
Node cur = root;
while (cur.Right != null)
{
pre = cur;
cur = cur.Right;
}
if (cur.Left != null)
{
cur = cur.Left;
while (cur.Right != null)
cur = cur.Right;
secondMax = cur.Value;
}
else
{
if (cur == root && pre == root)
//Only one node in BST
secondMax = int.MinValue;
else
secondMax = pre.Value;
}
return secondMax;
}
Алго может быть следующим:
1. find the largest number in the tree.
private static int findLargestValueInTree(Node root) {
while (root.right != null) {
root = root.right;
}
return root.data;
}
2. Find the largest number in the tree that is smaller than the number we found in step 1
public static int findSecondLargest(Node root, int largest, int current) {
while (root != null) {
if (root.data < largest) {
current = root.data;
root = root.right;
} else {
root = root.left;
}
}
return current;
}
'current' отслеживает текущее наибольшее число, которое меньше числа, найденного в шаге 1
Более простой итеративный подход с временной сложностью O (logN) и сложностью пространства O (1)
public static void main(String[] args) {
BinaryTreeNode result=isBinarySearchTree.secondLargest(rootNode);
System.out.println(result.data);
}
private BinaryTreeNode secondLargest(BinaryTreeNode node) {
BinaryTreeNode prevNode=null; //2nd largest Element
BinaryTreeNode currNode=node;
if(null == currNode)
return prevNode;
while(currNode.right != null){
prevNode=currNode;
currNode=currNode.right;
}
if(currNode.left != null){
currNode=currNode.left;
while(currNode.right != null){
currNode=currNode.right;
}
prevNode=currNode;
}
return prevNode;
}
Простая реализация javascript.
function Node (value, left, right) {
this.value = value;
this.left = left;
this.right = right;
}
function second (node, prev, wentLeft) {
if (node.right) {
return second(node.right, node, wentLeft);
} else if (node.left) {
return second(node.left, node, true);
} else {
if (wentLeft) return node.value;
return prev.value;
}
}
second(root);
Один вариант обхода:
public Tree GetSecondMax(Tree root)
{
Tree parentOfMax = null;
var maxNode = GetMaxNode(root, ref parentOfMax);
if (maxNode == root || maxnode.left != null)
{
// if maximum node is root or have left subtree, then return maximum from left subtree
return GetMaxNode(maxnode.left, ref parentOfMax);
}
// if maximum node is not root, then return parent of maximum node
return parentOfMax;
}
private Tree GetMaxNode(Tree root, ref Tree previousNode)
{
if (root == null || root.right == null)
{
// The most right element have reached
return root;
}
// we was there
previousNode = root;
return GetMaxNode(root.right, ref previousNode);
}
int getmax(node *root)
{
if(root->right == NULL)
{
return root->d;
}
return getmax(root->right);
}
int secondmax(node *root)
{
if(root == NULL)
{
return -1;
}
if(root->right == NULL && root->left != NULL)
{
return getmax(root->left);
}
if(root->right != NULL)
{
if(root->right->right == NULL && root->right->left == NULL)
{
return root->d;
}
}
return secondmax(root->right);
}
Очень интуитивный способ думать об этом - это рассмотрение следующих двух случаев. Пусть вторая по величине Node как S и наибольшая Node как L.
i) S вставлен в BST "раньше", чем L. ii) S вставляется в BST "позже", чем L.
В первом случае очевидно, что L - правый ребенок S. Это потому, что любой Node за исключением L меньше S, поэтому не будет помещен в правую часть S. Поэтому, когда L, он будет правильным потомком S.
Во втором случае, к моменту ввода S, L будет самым большим Node в BST. Очевидно, что L не будет иметь правильного ребенка, потому что он является самым большим. Однако L может иметь собственное левое поддерево. Когда S вставлен, S будет следовать по "правильному пути", пока не встретит L, а затем поверните налево, чтобы перейти в левое поддерево L. Здесь мы знаем, что все узлы в левом поддереве слева меньше S, поэтому S будет самым правым Node в поддереве.
int getSecondLargest(Node root){
if(root==null)
return 0;
Node curr=root;
Node prev=root;
//Go to the largest node
while(curr.right != null){
prev = curr;
curr= curr.right;
}
//If largest Node has left child, Then largest element of tree with its root as largest.left will be the second largest number.
if(curr.left == null)
return prev.data;
else
return findLargest(curr.left);
}
int findLargest(Node root){
// No need toi check for null condition as in getSecondLargest method, its already done.
Node curr=root;
//To find largest just keep on going to right child till leaf is encountered.
while(curr.right != null){
curr = curr.right;
}
return curr.data;
}
Я бы сделал это, пройдя хотя бы дерево от самого большого до самого маленького элемента и возвращающее значение, когда спрошено положение достигнуто. Я выполнил аналогичную задачу для второго по величине значения.
void BTree::findSecondLargestValueUtil(Node* r, int &c, int &v)
{
if(r->right) {
this->findSecondLargestValueUtil(r->right, c, v);
}
c++;
if(c==2) {
v = r->value;
return;
}
if(r->left) {
this->findSecondLargestValueUtil(r->left, c, v);
}
}
int BTree::findSecondLargestValue()
{
int c = 0;
int v = -1;
this->findSecondLargestValueUtil(this->root, c, v);
return v;
}
Этот алгоритм запускается на дереве и возвращает наибольший элемент в Item1 и второй по величине в Item2.
Сортировка вызовов O (1), поскольку они не зависят от размера дерева.
Таким образом, общая временная сложность O (N) и сложность пространства O (log (N)), когда дерево сбалансировано.
public static Tuple<int, int> SecondLargest(TreeNode<int> node)
{
int thisValue = node.Value;
if ((node.Left == null || node.Left.Right == null) && node.Right == null)
{
return new Tuple<int, int>(thisValue, -int.MaxValue);
}
else if (node.Left == null || node.Left.Right == null)
{
Tuple<int, int> right = SecondLargest(node.Right);
List<int> sortLargest = new List<int>(new int[] { right.Item1, right.Item2, thisValue });
sortLargest.Sort();
return new Tuple<int, int>(sortLargest[2], sortLargest[1]);
}
else if (node.Right == null)
{
Tuple<int, int> left = SecondLargest(node.Left.Right);
List<int> sortLargest = new List<int>(new int[] { left.Item1, left.Item2, thisValue });
sortLargest.Sort();
return new Tuple<int, int>(sortLargest[2], sortLargest[1]);
}
else
{
Tuple<int, int> left = SecondLargest(node.Left.Right);
Tuple<int, int> right = SecondLargest(node.Right);
List<int> sortLargest = new List<int>(new int[] { left.Item1, left.Item2, right.Item1, right.Item2, thisValue });
sortLargest.Sort();
return new Tuple<int, int>(sortLargest[4], sortLargest[3]);
}
}
Вы близки к правильному ответу.
Вот моя попытка интуитивного ответа.
Наибольший node самый правый node.
Что бы ни было под самым большим node левым поддеревом больше всех элементов, кроме самого правого node. Поэтому наибольший node в этом поддереве есть ответ.
Если левого поддерева нет, то родительский элемент справа больше node является тем, который больше всех остальных узлов, кроме самого правого node.