LeetCode 510. Inorder Successor in BST II
原题链接在这里:https://leetcode.com/problems/inorder-successor-in-bst-ii/
题目:
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
The successor of a node p
is the node with the smallest key greater than p.val
.
You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node.
Example 1:
Input:
root = {"$id":"1","left":{"$id":"2","left":null,"parent":{"$ref":"1"},"right":null,"val":1},"parent":null,"right":{"$id":"3","left":null,"parent":{"$ref":"1"},"right":null,"val":3},"val":2}
p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of Node type.
Example 2:
Input:
root = {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":{"$id":"4","left":null,"parent":{"$ref":"3"},"right":null,"val":1},"parent":{"$ref":"2"},"right":null,"val":2},"parent":{"$ref":"1"},"right":{"$id":"5","left":null,"parent":{"$ref":"2"},"right":null,"val":4},"val":3},"parent":null,"right":{"$id":"6","left":null,"parent":{"$ref":"1"},"right":null,"val":6},"val":5}
p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer isnull
.
Example 3:
Input:
root = {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":{"$id":"4","left":null,"parent":{"$ref":"3"},"right":null,"val":2},"parent":{"$ref":"2"},"right":{"$id":"5","left":null,"parent":{"$ref":"3"},"right":null,"val":4},"val":3},"parent":{"$ref":"1"},"right":{"$id":"6","left":null,"parent":{"$ref":"2"},"right":{"$id":"7","left":{"$id":"8","left":null,"parent":{"$ref":"7"},"right":null,"val":9},"parent":{"$ref":"6"},"right":null,"val":13},"val":7},"val":6},"parent":null,"right":{"$id":"9","left":{"$id":"10","left":null,"parent":{"$ref":"9"},"right":null,"val":17},"parent":{"$ref":"1"},"right":{"$id":"11","left":null,"parent":{"$ref":"9"},"right":null,"val":20},"val":18},"val":15}
p = 15
Output: 17
Example 4:
Input:
root = {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":{"$id":"4","left":null,"parent":{"$ref":"3"},"right":null,"val":2},"parent":{"$ref":"2"},"right":{"$id":"5","left":null,"parent":{"$ref":"3"},"right":null,"val":4},"val":3},"parent":{"$ref":"1"},"right":{"$id":"6","left":null,"parent":{"$ref":"2"},"right":{"$id":"7","left":{"$id":"8","left":null,"parent":{"$ref":"7"},"right":null,"val":9},"parent":{"$ref":"6"},"right":null,"val":13},"val":7},"val":6},"parent":null,"right":{"$id":"9","left":{"$id":"10","left":null,"parent":{"$ref":"9"},"right":null,"val":17},"parent":{"$ref":"1"},"right":{"$id":"11","left":null,"parent":{"$ref":"9"},"right":null,"val":20},"val":18},"val":15}
p = 13
Output: 15
Note:
- If the given node has no in-order successor in the tree, return
null
. - It's guaranteed that the values of the tree are unique.
- Remember that we are using the
Node
type instead ofTreeNode
type so their string representation are different.
Follow up:
Could you solve it without looking up any of the node's values?
题解:
Successor could exist in 2 possible positions.
If x has right child, successor must be below its right child, x.right, then keep going down left.
Otherwise, successor could be x going up untill hitting first ancestor through left edge. There may be case that it keeps going up through right edge, then there is no successor.
Time Complexity: O(h). h is the height of tree.
Space: O(1).
AC Java:
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
};
*/
class Solution {
public Node inorderSuccessor(Node x) {
if(x == null){
return x;
} if(x.right != null){
Node suc = x.right;
while(suc.left != null){
suc = suc.left;
} return suc;
} while(x.parent != null && x.parent.right == x){
x = x.parent;
} return x.parent;
}
}
最新文章
- HTTP API开发
- orientationchange不管用啊
- sql语句查询经纬度范围
- Redis for Windows(C#缓存)安装和使用
- OpenRisc-67-OR的汇编
- 5451 HDU Best Solver
- 关于select
- 再议Swift操作符重载
- 初步swift该研究指出语言(基本数据类型)
- Javassist进行方法插桩
- C++版 - 剑指offer 面试题7:用两个栈实现队列 题解
- Solve Error: Unhandled exception at 0x00905a4d in xxx.exe: 0xC0000005: Access violation.
- 原生js中用Ajax进行get传参
- python 内置函数总结(大部分)
- hdu 2544 hdu 1874 poj 2387 Dijkstra 模板题
- linux配置防火墙,开启端口
- vim 查找替换批量替换
- Kubernetes 部署 1.9.7 高可用版
- 【MySQL】MySQL之MySQL5.7中文乱码
- 微信小程序 - 实现购物车结算