使用隊列在BST中反轉路徑  


難度級別 中烘焙
經常問 彭博社 谷歌 雜貨店 匯豐銀行 Microsoft微軟 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時BST中的第K個最大元素

使用隊列在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是二進制搜索樹中的節點數。

也可以看看
從鏈接列表表示構造完整的二叉樹

參考