文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一棵二叉搜索樹和其中的一個(gè)節(jié)點(diǎn) node ，找到該節(jié)點(diǎn)在樹中的中序后繼。

如果節(jié)點(diǎn)沒有中序后繼，請(qǐng)返回 null 。

一個(gè)結(jié)點(diǎn) node 的中序后繼是鍵值比 node.val大所有的結(jié)點(diǎn)中鍵值最小的那個(gè)。

你可以直接訪問結(jié)點(diǎn)，但無法直接訪問樹。
每個(gè)節(jié)點(diǎn)都會(huì)有其父節(jié)點(diǎn)的引用。節(jié)點(diǎn)定義如下：

class Node {public int val;public Node left;public Node right;public Node parent; }

進(jìn)階：
你能否在不訪問任何結(jié)點(diǎn)的值的情況下解決問題?

示例 1:

輸入: tree = [2,1,3], node = 1 輸出: 2 解析: 1 的中序后繼結(jié)點(diǎn)是 2 。 注意節(jié)點(diǎn)和返回值都是 Node 類型的。

示例 2:

輸入: tree = [5,3,6,2,4,null,null,1], node = 6 輸出: null 解析: 該結(jié)點(diǎn)沒有中序后繼，因此返回 null 。

示例 3:

輸入: tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 15 輸出: 17

示例 4:

輸入: tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 13 輸出: 15提示： -10^5 <= Node.val <= 10^5 1 <= Number of Nodes <= 10^4 樹中各結(jié)點(diǎn)的值均保證唯一。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/inorder-successor-in-bst-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

類似題目：LeetCode 285. 二叉搜索樹中的順序后繼（中序遍歷）

• 這題不知道根節(jié)點(diǎn)，我們先查看有沒有右節(jié)點(diǎn)，比其大的，最小值，肯定在右子樹里
• 如有右子樹，則，一直找右子樹的左分支，找到底就是答案
• 沒有右子樹，那就找第一個(gè)比節(jié)點(diǎn)值大的祖父節(jié)點(diǎn)

/* // Definition for a Node. class Node { public:int val;Node* left;Node* right;Node* parent; }; */class Solution { public:Node* inorderSuccessor(Node* node) {if(!node->right)//右節(jié)點(diǎn)比其大，沒有右節(jié)點(diǎn),那就查上面的多層祖父節(jié)點(diǎn){int v = node->val;while(node->parent && node->parent->val < v){node = node->parent;}return node->parent;}Node* cur = node->right, *prev = NULL;while(cur){prev = cur;cur = cur->left;}return prev;} };

32 ms 11.6 MB

• 不訪問節(jié)點(diǎn)的值

/* // Definition for a Node. class Node { public:int val;Node* left;Node* right;Node* parent; }; */class Solution { public:Node* inorderSuccessor(Node* node) {if(!node->right)//右節(jié)點(diǎn)比其大，沒有右節(jié)點(diǎn),那就查上面的多層祖父節(jié)點(diǎn){while(node->parent && node->parent->left != node){ //當(dāng)遇到父節(jié)點(diǎn)的左節(jié)點(diǎn)是 當(dāng)前node時(shí) 即找到node = node->parent;}return node->parent;}Node* cur = node->right, *prev = NULL;while(cur){prev = cur;cur = cur->left;}return prev;} };

---

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

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 510. 二叉搜索树中的中序后继 II（查找右子树或者祖父节点）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。