题目描述
给定一棵二叉树的其中一个节点,请找出中序遍历序列的下一个节点。
样例
假定二叉树是:[2, 1, 3, null, null, null, null], 给出的是值等于2的节点。
则应返回值等于3的节点。
解释:该二叉树的结构如下,2的后继节点是3。
2
/ \
1 3
算法1
(JAVA) $O(h)$
class Solution {
public TreeNode inorderSuccessor(TreeNode p) {
//存在右子树,则为右子树最小的
if(p.right != null){
p = p.right;
while(p.left != null){
p = p.left;
}
return p;
}
while(p.father != null && p.father.right == p){
p = p.father;
}
return p.father;
}
}