LeetCode 510. 二叉搜索树中的中序后继 II（查找右子树或者祖父节点）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

给定一棵二叉搜索树和其中的一个节点 node ，找到该节点在树中的中序后继。

如果节点没有中序后继，请返回 null 。

一个结点 node 的中序后继是键值比 node.val大所有的结点中键值最小的那个。

你可以直接访问结点，但无法直接访问树。
每个节点都会有其父节点的引用。节点定义如下：

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

进阶：
你能否在不访问任何结点的值的情况下解决问题?

示例 1:

输入: tree = [2,1,3], node = 1 输出: 2 解析: 1 的中序后继结点是 2 。 注意节点和返回值都是 Node 类型的。

示例 2:

输入: tree = [5,3,6,2,4,null,null,1], node = 6 输出: null 解析: 该结点没有中序后继，因此返回 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 树中各结点的值均保证唯一。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/inorder-successor-in-bst-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：LeetCode 285. 二叉搜索树中的顺序后继（中序遍历）

• 这题不知道根节点，我们先查看有没有右节点，比其大的，最小值，肯定在右子树里
• 如有右子树，则，一直找右子树的左分支，找到底就是答案
• 没有右子树，那就找第一个比节点值大的祖父节点

/* // 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)//右节点比其大，没有右节点,那就查上面的多层祖父节点{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

• 不访问节点的值

/* // 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)//右节点比其大，没有右节点,那就查上面的多层祖父节点{while(node->parent && node->parent->left != node){ //当遇到父节点的左节点是 当前node时 即找到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/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的LeetCode 510. 二叉搜索树中的中序后继 II（查找右子树或者祖父节点）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。