N-й по величине элемент в бинарном дереве поиска

Question

Как найти N-й по величине узел в BST?

Сохраняю ли я переменную count при выполнении обхода по порядку BST? Вернуть элемент, когда count = N ???

Answer 1

Используйте перевернутый inorder tranversal. То есть сначала перейдите к правому ребенку, а не к левому. рекурсивно это можно получить следующим образом: Самая важная проблема, которую необходимо использовать при рассмотрении рекурсивного решения - глобальный счет.

reverseInorder(root){
 if(root!=null){
reverseInorder(root->rightChild);
self
reverseInorder(root->leftChild);
}
}

Решение в Java

    package datastructure.binaryTree;

import datastructure.nodes.BinaryTreeNode;


public class NthElementFromEnd {
    private BinaryTree tree=null;
    int currCount=0;
    public NthElementFromEnd(int[] dataArray) {
        this.tree=new BinaryTree(dataArray);

    }
    private void getElementFromEnd(int n){
        getElementFromEnd(this.tree.getRoot(),n);
    }
    private void getElementFromEnd(BinaryTreeNode node,int n){
        if(node!=null){
            if(currCount<n)
            getElementFromEnd(node.getRightChild(),n);
            currCount++;

            if(currCount==n)
            {
                System.out.print(" "+node.getData());
                return;
            }
            if(currCount<n)
            getElementFromEnd(node.getLeftChild(),n);
        }
    }

    public static void main(String args[]){
        int data[]={1,2,3,4,5,6,7,8,9};
        int n=2;
        new NthElementFromEnd(data).getElementFromEnd(n);
    }
}