文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個二叉搜索樹和其中的某一個結點，請你找出該結點在樹中順序后繼的節點。

結點 p 的后繼是值比 p.val 大的結點中鍵值最小的結點。

示例 1:

輸入: root = [2,1,3], p = 1 輸出: 2 解析: 這里 1 的順序后繼是 2。 請注意 p 和返回值都應是 TreeNode 類型。

示例 2:

輸入: root = [5,3,6,2,4,null,null,1], p = 6 輸出: null 解析: 因為給出的結點沒有順序后繼，所以答案就返回 null 了。注意: 假如給出的結點在該樹中沒有順序后繼的話，請返回 null 我們保證樹中每個結點的值是唯一的

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/inorder-successor-in-bst
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：LeetCode 510. 二叉搜索樹中的中序后繼 II（查找右子樹或者祖父節點）

• 循環版中序遍歷，找到p節點后的下一個即是答案

class Solution { public:TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {if(!root) return NULL;stack<TreeNode*> stk;TreeNode *cur;bool found = false;while(root || !stk.empty()){while(root){stk.push(root);root = root->left;}cur = stk.top();if(found)return cur;stk.pop();root = cur->right;if(cur == p)found = true;}return NULL;} };

44 ms 22.9 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 285. 二叉搜索树中的顺序后继（中序遍历）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。