面试题 04.06. 后继者
设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
如果指定节点没有对应的“下一个”节点，则返回null。
示例 1:
输入: root = [2,1,3], p = 1
2
/ \
1 3
输出: 2
示例 2:
输入: root = [5,3,6,2,4,null,null,1], p = 6
5
/ \
3 6
/ \
2 4
/
1
输出: null
原站题解
java 解法, 执行用时: 2 ms, 内存消耗: 42.3 MB, 提交时间: 2022-11-29 15:45:46
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode successor = null;
if (p.right != null) {
successor = p.right;
while (successor.left != null) {
successor = successor.left;
}
return successor;
}
TreeNode node = root;
while (node != null) {
if (node.val > p.val) {
successor = node;
node = node.left;
} else {
node = node.right;
}
}
return successor;
}
}
python3 解法, 执行用时: 72 ms, 内存消耗: 19 MB, 提交时间: 2022-11-29 15:44:30
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
successor = None
if p.right:
successor = p.right
while successor.left:
successor = successor.left
return successor
node = root
while node:
if node.val > p.val:
successor = node
node = node.left
else:
node = node.right
return successor
javascript 解法, 执行用时: 88 ms, 内存消耗: 51 MB, 提交时间: 2022-11-29 15:44:15
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @return {TreeNode}
*/
var inorderSuccessor = function(root, p) {
let successor = null;
if (p.right) {
successor = p.right;
while (successor.left) {
successor = successor.left;
}
return successor;
}
let node = root;
while (node) {
if (node.val > p.val) {
successor = node;
node = node.left;
} else {
node = node.right;
}
}
return successor;
};
golang 解法, 执行用时: 24 ms, 内存消耗: 6.9 MB, 提交时间: 2022-11-29 15:44:01
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderSuccessor(root, p *TreeNode) *TreeNode {
var successor *TreeNode
if p.Right != nil {
successor = p.Right
for successor.Left != nil {
successor = successor.Left
}
return successor
}
node := root
for node != nil {
if node.Val > p.Val {
successor = node
node = node.Left
} else {
node = node.Right
}
}
return successor
}
golang 解法, 执行用时: 20 ms, 内存消耗: 6.9 MB, 提交时间: 2022-11-29 15:43:33
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderSuccessor(root, p *TreeNode) *TreeNode {
st := []*TreeNode{}
var pre, cur *TreeNode = nil, root
for len(st) > 0 || cur != nil {
for cur != nil {
st = append(st, cur)
cur = cur.Left
}
cur = st[len(st)-1]
st = st[:len(st)-1]
if pre == p {
return cur
}
pre = cur
cur = cur.Right
}
return nil
}
javascript 解法, 执行用时: 92 ms, 内存消耗: 50.8 MB, 提交时间: 2022-11-29 15:43:16
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @return {TreeNode}
*/
var inorderSuccessor = function(root, p) {
const stack = [];
let prev = null, curr = root;
while (stack.length || curr) {
while (curr) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
if (prev === p) {
return curr;
}
prev = curr;
curr = curr.right;
}
return null;
};
python3 解法, 执行用时: 68 ms, 内存消耗: 19 MB, 提交时间: 2022-11-29 15:41:58
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
st, pre, cur = [], None, root
while st or cur:
while cur:
st.append(cur)
cur = cur.left
cur = st.pop()
if pre == p:
return cur
pre = cur
cur = cur.right
return None