为什么我们要检查 n.parent == null？

Question

我正在查找二叉搜索树中给定节点的 'next' 节点（即有序后继节点）。

为什么在下面给出的代码中使用这个条件：

if (n.parent == null || n.right != null)

我的问题是：我们为什么要检查 n.parent == null ？

完整代码：

public static TreeNode inorderSucc(TreeNode n) { 
    if (n == null) return null;

    // Found right children -> return left most node of right subtree
    if (n.parent == null || n.right != null) { 
        return leftMostChild(n.right); 
    } else { 
        TreeNode q = n;
        TreeNode x = q.parent;
        // Go up until we’re on left instead of right
        while (x != null && x.left != q) {
            q = x;
            x = x.parent;
        }
        return x;
    }  
} 

public static TreeNode leftMostChild(TreeNode n) {
    if (n == null) {
        return null;
    }
    while (n.left != null) {
        n = n.left; 
    }
    return n; 
}

Answer 1

if (n.parent == null || n.right != null)

检查 n 是否是 root 节点并且它有右子树。

为什么我们要检查 n.parent == null？

Why are we checking for n.parent == null?

java

tree

graph