思路
给定一棵二叉树的其中一个节点,二叉树的下一个节点即中序遍历序列的下一个节点。
两个情况:有无右孩子
时间复杂度
单次求时间复杂度O(h)
平衡树为O(logn)
把每个点的后继都求一遍,总的复杂度为O(n)
class Solution {
public TreeNode inorderSuccessor(TreeNode p) {
//情况1:存在右孩子,其后继是右子树中最左侧的节点
//中序遍历:左子树 根 右子树
if(p.right != null){
p = p.right;
while(p.left != null){//当p的左节点不为空
p = p.left;
}
return p;
}
//情况2:不存在右孩子,给定节点如果有父节点则一直往左上方走,后继结点为最近一个有左孩子的父节点
while(p != null && p.father != null && p == p.father.right){//给定节点不为空且有父节点且为父节点的右节点
p = p.father;
}
return p.father;
}
}