二叉搜索树的中序后继节点（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

Arnab Chakraborty

更新时间： 2020 年 11 月 18 日

125 次浏览

开始你的 事业

完成课程，获得认证

开始