使用队列在BST中反转路径


难度级别 中等
经常问 彭博 谷歌 杂货店 汇丰银行 微软 Target公司
二进制搜索树 二叉树 队列 穿越 树遍历

反向使用队列问题在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(root,target)

  1. 如果根为空,则返回。
  2. 如果root的值等于目标值,则将root的值推入队列,并用队列前面的元素替换root的值。 删除队列前面的元素。
  3. 否则,如果root的值小于目标,则将root的值推入队列,递归调用root的左孩子的versePathBST,然后将root的值替换为队列前面的元素。 同样,删除队列前面的元素。
  4. 否则,将根的值推送到队列,递归调用root的右子对象的versePathBST,然后用队列前面的元素替换根的值。 同样,删除队列前面的元素。

使用队列在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

使用Queue在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(log n)
空间复杂度= O(log n)
其中,n是二进制搜索树中的节点数。

參考資料