큐를 사용하여 BST에서 경로 반전

큐 문제를 사용하는 BST의 경로를 반대로 우리는 이진 검색을 제공했습니다. 나무 및 노드, 쓰기 연산 루트에서 주어진 노드로의 경로를 반전합니다. 노드가 BST에 존재한다고 가정하십시오.

예

입력

핀

대상 노드 = 12
산출

핀

순서대로 순회 반전 전
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. 루트가 null이면 반환합니다.
2. 루트의 값이 대상과 같으면 루트의 값을 큐에 푸시하고 루트의 값을 큐 맨 앞의 요소로 바꿉니다. 대기열 앞에있는 요소를 제거합니다.
3. 그렇지 않으면 루트의 값이 대상보다 작 으면 루트의 값을 큐에 푸시하고 루트의 왼쪽 자식에 대해 reversePathBST를 재귀 적으로 호출 한 다음 루트의 값을 큐 앞의 요소로 바꿉니다. 또한 대기열 맨 앞에있는 요소를 제거하십시오.
4. 그렇지 않으면 루트의 값을 큐에 푸시하고 루트의 오른쪽 자식에 대해 reversePathBST를 재귀 적으로 호출 한 다음 큐의 맨 앞에있는 요소로 루트의 값을 바꿉니다. 또한 대기열 맨 앞에있는 요소를 제거하십시오.

대기열을 사용하여 BST에서 경로 반전을위한 JAVA 코드

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

큐를 사용하여 BST에서 경로 반전을위한 C ++ 코드

#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은 이진 검색 트리의 노드 수입니다.

참조