Ən yaxın Binar Axtarış Ağacı Dəyəri Leetcode Həlli

Problem bəyanat :

Ən yaxın Binar Axtarış Ağacı Dəyəri Leetcode Həlli – Nəzərə alınmaqla kök bir ikili axtarış ağacı və bir hədəf dəyər, qayıdış BST-də ən yaxın olan dəyər hədəf.

Misal:

Məsələn 1

Pin

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

Məsələn 2

Input: root = [1], target = 4.428571
Output: 1

Məhdudiyyətlər:

Pin

İzahat:

• Verilmişdir kök ikili axtarış ağacının və a hədəf dəyər.
• Bizə qayıtmaq lazımdır node dəyəri of BST ki, ən yaxın hədəfə.
• saata Misal 1, hədəf = 3.714286, və dəyərləri olan qovşaqlar 3 və 4 hədəfə daha yaxın olan mümkün qovşaqlardır.
• Ancaq ən yaxın qovşaq 4-dür hədəflə.

               3 node üçün,  ən yaxınlıq=|3.714286 – 3| = 0.714286

              4 node üçün,  ən yaxınlıq=|3.714286 – 4| = 0.285714

Müşahidə:

• BST-də bütün sol uşaq qovşaqların dəyəri var kiçik ki, daha ana dəyər, və həmçinin, bütün sağ uşaq düyünləri dəyəri var böyük ki, daha ana dəyər.
• Əgər biz bir Sifarişlə traversal, biz BST-də qovşaqların olduğunu görə bilərik artan ardıcıllıqla sıralanır.

Yanaşma:

• Yuxarıdakı müşahidədən biz iterativ olaraq İkili Axtarış alqoritmini istifadə edə bilərik.
• Biz BST-ni kökdən səyahət edəcəyik və keçərkən də edəcəyik yaxınlığı hesablayın hədəfi olan hər node.
• Kök dəyəri olarsa bərabər sonra hədəfə kök.val.

                             if(root.val==target) root.val-i qaytarın;

• Kök dəyəri olarsa kiçik Hədəfdən daha sonra gedəcəyik sağ uşaq kökdən.

                               əgər (root.val root=root.right;

• Kök dəyəri olarsa böyük Hədəfdən daha sonra gedəcəyik sol uşaq kökdən.

                              if(root.val>hədəf) root=root.left;

Ən yaxın İkili Axtarış Ağacı Dəyəri üçün Kod:

Ən yaxın Binar Axtarış Ağacı Dəyəri üçün Java Kodu

class Solution {
    public int closestValue(TreeNode root, double target) {
        double closestValue=Integer.MAX_VALUE;
        int closestNode=root.val;
        while(root!=null){
            if(closestValue>Math.abs(target-root.val)){
                closestValue=Math.abs(target-root.val);
                closestNode=root.val;
            }
            if(root.val==target)return root.val;
            if(root.val<target){
                root=root.right;
            }
            else if(target<root.val){
                root=root.left;
            }
        }
        return closestNode;
    }
}

C + + Ən yaxın İkili Axtarış Ağacı Dəyəri üçün Kod

class Solution {
public:
    int closestValue(TreeNode* root, double target) {
        double closestValue=INT_MAX;
        int closestNode=root->val;
        while(root!=NULL){
            if(closestValue>abs(target-root->val)){
                closestValue=abs(target-root->val);
                closestNode=root->val;
            }
            if(root->val==target)return root->val;
            if(root->val<target){
                root=root->right;
            }
            else if(target<root->val){
                root=root->left;
            }
        }
        return closestNode;
    }
};

Ən yaxın Binar Axtarış Ağacı Dəyəri üçün Mürəkkəblik Təhlili Leetcode Həlli:

Zamanın mürəkkəbliyi

O(H), çünki biz kökdən yarpağa enirik.

Kosmik Mürəkkəblik 

O(1), sabit fəza.