資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究二叉搜尋樹的中序後繼節點（C++ 版）
假設我們有一個二叉搜尋樹和其中的一個節點，我們必須在二叉搜尋樹中搜索該節點的中序後繼節點。正如我們所知，節點 p 的後繼節點是鍵小於 p.val 的最小鍵的節點。
所以，如果輸入為 root = [2,1,3], p = 1,
那麼輸出將是 2,
為了解決這個問題，我們將按照以下步驟進行操作 -
定義遞迴方法 inorderSuccessor()，它將採用根和 p
如果 root 為空，那麼 -
返回 null
如果 root 的 val <= p 的 val，那麼 -
返回 inorderSuccessor(root 的右子樹, p)
否則
option := inorderSuccessor(root 的左子樹, 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;
}輸入
{2,1,3},1輸出
2
更新時間： 2020 年 11 月 18 日
125 次瀏覽
廣告