C++程式：查詢二叉搜尋樹中的中序後繼

假設我們有一個二叉搜尋樹 BST 和另一個節點的值，我們需要在 BST 中找到該節點的中序後繼。眾所周知，節點 p 的後繼是鍵值大於 p 的值且最小的節點。

因此，如果輸入如下所示：

並且 p = 1，則輸出將為 2，

為了解決這個問題，我們將遵循以下步驟：

  • 定義遞迴方法 inorderSuccessor()，它將接收根節點和 p
  • 如果根節點為空，則
    • 返回 null
  • 如果根節點的值小於等於 p 的值，則
    • 返回 inorderSuccessor(根節點的右子樹, p)
  • 否則
    • option := inorderSuccessor(根節點的左子樹, p)
    • 返回 (如果 option 為零，則返回根節點，否則返回 option)

讓我們看看下面的實現，以便更好地理解：

示例

 線上演示

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
class Solution {
   public:
   TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
      if(!root) return NULL;
         if(root->val <= p->val){
            return inorderSuccessor(root->right, p);
         }else{
            TreeNode* option = inorderSuccessor(root->left, p);
            return !option ? root : option;
      }
   }
};
main(){
   TreeNode *root = new TreeNode(2);
   root->left = new TreeNode(1);
   root->right = new TreeNode(3);
   TreeNode *p = root->left;
   Solution ob;
   cout << (ob.inorderSuccessor(root, p))->val;
}

輸入

TreeNode *root = new TreeNode(2);
root->left = new TreeNode(1);
root->right = new TreeNode(3);
1

輸出

2

更新於: 2020-11-19

589 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告