做产品网站需要注意,企业网站管理系统多站多语言版,基于jsp企业网站开发设计答辩ppt,医疗器械做网站备案文章目录1. 题目2. 解题1. 题目
给定一棵二叉搜索树和其中的一个节点 node #xff0c;找到该节点在树中的中序后继。
如果节点没有中序后继#xff0c;请返回 null 。
一个结点 node 的中序后继是键值比 node.val大所有的结点中键值最小的那个。
你可以直接访问结点找到该节点在树中的中序后继。
如果节点没有中序后继请返回 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阿明一起加油、一起学习进步
