הפוך נתיב ב- BST באמצעות תור


רמת קושי בינוני
נשאל לעתים קרובות בלומברג Google מגדלים HSBC מיקרוסופט תאגיד היעד
עץ חיפוש בינארי עץ בינארי תור מעבר עֵץ מעבר עץ

הפוך נתיב ב- BST באמצעות בעיית תור נתנו חיפוש בינארי עֵץ וצומת, כתוב אַלגוֹרִיתְם כדי להפוך את הנתיב מהשורש לצומת הנתון. נניח שהצומת קיים ב- BST.

דוגמה

קֶלֶט

הפוך נתיב ב- BST באמצעות תור

צומת יעד = 12
תְפוּקָה

הפוך נתיב ב- BST באמצעות תור

בסדר חצייה לפני המהפך
3 4 7 8 9 12 15 18
מעבר לפי הזמנה לאחר היפוך
3 4 7 12 15 8 9 18

אלגוריתם להיפוך נתיב ב- BST באמצעות תור

היפוך נתיב מהשורש לצומת זהה להחזרת האלמנטים של הצמתים בנתיב מהשורש לצומת. לדוגמא, אם הנתיב מהשורש לצומת הוא 5 -> 10 -> 15 -> 20, אז היפוך הנתיב זהה להיפוך הנתונים. אז הנתיב ההפוך הוא 20 -> 15 -> 10 -> 5.
הרעיון הוא לדחוף את כל הערכים של הצמתים המגיעים בדרך מהשורש לצומת הנתון בתור ולאחר הדחיפה החלף את הצומת הנוכחי באלמנט שבחזית התור.

reversePathBST (שורש, יעד)

  1. אם השורש אפס, חזור.
  2. אם ערך השורש שווה ליעד, דחף את ערך השורש לתור והחלף את ערך השורש באלמנט שבחזית התור. הסר את האלמנט בקדמת התור.
  3. אחרת אם הערך של השורש נמוך מהיעד, ואז דחף את ערך השורש לתור, התקשר reversePathBST באופן רקורסיבי לילד השמאלי של השורש ואז החלף את ערך השורש באלמנט שבחזית התור. כמו כן, הסר את האלמנט בקדמת התור.
  4. אחרת דחף את ערך השורש לתור, התקשר ל- reversePathBST באופן רקורסיבי לילד הימני של השורש ואז החלף את ערך השורש באלמנט שנמצא בקדמת התור. כמו כן, הסר את האלמנט בקדמת התור.

קוד JAVA להיפוך נתיב ב- BST באמצעות תור

import java.util.LinkedList;
import java.util.Queue;

public class ReverseAPathInBSTUsingQueue {
    // class representing node of a BST
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // queue used to reverse the path in BST
    private static Queue<Integer> queue;

    // function to print inorder traversal of a tree
    private static void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    private static void reversePath(Node root, int target) {
        // if root is null return
        if (root == null) {
            return;
        }

        // add root's data to queue
        queue.add(root.data);

        if (root.data == target) {
            // Base case
        } else if (root.data > target) {
            // target is in left sub tree
            reversePath(root.left, target);
        } else {
            // target is in right sub tree
            reversePath(root.right, target);
        }

        // replace root's data with front of queue
        root.data = queue.poll();
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(8);
        root.left = new Node(4);
        root.right = new Node(9);
        root.left.left = new Node(3);
        root.left.right = new Node(7);
        root.right.right = new Node(15);
        root.right.right.left = new Node(12);
        root.right.right.right = new Node(18);

        // inorder traversal before reversing
        System.out.println("Inorder before reversal");
        inorder(root);
        System.out.println();

        queue = new LinkedList<>();
        reversePath(root, 12);

        // inorder traversal after reversing
        System.out.println("Inorder after reversal");
        inorder(root);
        System.out.println();
    }
}
Inorder before reversal
3 4 7 8 9 12 15 18 
Inorder after reversal
3 4 7 12 15 8 9 18

קוד C ++ להיפוך נתיב ב- BST באמצעות תור

#include <bits/stdc++.h>
using namespace std;

// class representing node of a BST
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// queue used to reverse the path in BST
queue<int> q;

void inorder(Node *root) {
    if (root != NULL) {
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

void reversePath(Node *root, int target) {
    // if root is null return
    if (root == NULL) {
        return;
    }
    
    // add root's data to queue
    q.push(root->data);
    
    if (root->data == target) {
        // Base case
    } else if (root->data > target) {
        // target is in left sub tree
        reversePath(root->left, target);
    } else {
        // target is in right sub tree
        reversePath(root->right, target);
    }
    
    // replace root's data with front of queue
    root->data = q.front();
    q.pop();
}

int main() {
    // Example Tree
    Node *root = new Node(8);
    root->left = new Node(4);
    root->right = new Node(9);
    root->left->left = new Node(3);
    root->left->right = new Node(7);
    root->right->right = new Node(15);
    root->right->right->left = new Node(12);
    root->right->right->right = new Node(18);

    // inorder traversal before reversing
    cout<<"Inorder before reversal"<<endl;
    inorder(root);
    cout<<endl;
    
    reversePath(root, 12);

    // inorder traversal after reversing
    cout<<"Inorder after reversal"<<endl;
    inorder(root);
    cout<<endl;
    
    return 0;
}
Inorder before reversal
3 4 7 8 9 12 15 18 
Inorder after reversal
3 4 7 12 15 8 9 18

ניתוח מורכבות

מורכבות זמן = O (יומן n)
מורכבות שטח = O (יומן n)
כאשר n הוא מספר הצמתים בעץ החיפוש הבינארי.

הפניות