【leetcode】【剑指offer Ⅱ】053. 二叉搜索树中的中序后继

问题描述：

• 给定一棵二叉搜索树和其中的一个节点 p，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null。
  • 节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。

核心思路：

• 该题有两种解题方法。
• 方法一：中序遍历二叉搜索树，用两个变量记录当前节点与前一个节点。
  • 如果上一个访问的节点是节点 p，则当前访问节点是 p 的中序后继。
• 方法二：利用二叉搜索树的性质。
  • 如果 root -> val <= p -> val，则结果必定在 root 的右子树中。
  • 否则结果必定在 root 的左子树中或这就是 root。

代码实现：

• 方法一代码实现如下：

  class Solution
  {
  private:
      TreeNode* cur = nullptr;
      TreeNode* next = nullptr;
      void dfs(TreeNode* root, TreeNode* p)
      {
          if(!root) return;
          dfs(root->left, p);
          if(cur)
          {
              next = next ? next : root;
              return;
          }
          if(root == p) cur = p;
          dfs(root->right, p);
          return;
      }
  public:
      TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p)
      {
          dfs(root, p);
          return next;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25

• 方法二代码实现如下：【下述代码为递归版本，代码贴自评论区】

  class Solution {
  public:
      TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
          if (!root) return root;
  
          if (root -> val <= p -> val) 
              return inorderSuccessor(root -> right, p);
          
          auto left = inorderSuccessor(root -> left, p);
          return !left ? root : left;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12