模拟
二叉树的中序遍历:{ [左子树], 根节点, [右子树] }
如图所示二叉树的中序遍历:D, B, H, E, I, A, F, C, G
分三种情况:
- 如果该节点有右子树,那么下一个节点就是其右子树中最左边的节点;
- 如果该节点没有右子树,且是其父节点的左子节点,那么下一个节点就是其父节点;
- 如果该节点没有右子树,且是其父节点的右子节点,沿着父指针一直向上,直到找到一个是它父节点的左子节点的节点,如果这样的节点存在,那么这个节点的父节点即是所求。
例如:
- 情况 1:图中节点
B
的下一个节点是节点H
; - 情况 2:图中节点
H
的下一个节点是节点E
; - 情况 3:图中节点
I
的下一个节点是节点A
。
时空复杂度
- 时间复杂度:$O(height)$,其中 $height$ 是二叉树的高度
- 空间复杂度:$O(1)$
Java 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode father;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
/**
* 模拟
* 时间复杂度:O(height),height 为二叉树的高度
* 空间复杂度:O(1)
*/
public TreeNode inorderSuccessor(TreeNode p) {
TreeNode node = p;
// Case 1. 如果该节点有右子树,那么下一个节点就是其右子树中最左边的节点
if (node.right != null) {
node = node.right;
while (node.left != null) {
node = node.left;
}
return node;
}
// Case 3. 如果该节点没有右子树,且是其父节点的右子节点
// 沿着父指针一直向上,直到找到一个是它父节点的左子节点的节点
// 如果这样的节点存在,那么这个节点的父节点即是所求
while (node.father != null && node == node.father.right) {
node = node.father;
}
// Case 2. 如果该节点没有右子树,且是其父节点的左子节点,那么下一个节点就是其父节点
return node.father;
}
}