Next Node

出处

In-order traverse a binary tree with parent links, find the next node to visit given a specific node.

Solution

根据中序遍历的性质,我们可以分几种情况来考虑目标节点与给定节点的关系:1,如果该节点有右子树,那么,中序后继节点就是右子树中最左的节点。2,如果没有右子树,那么考虑该节点与其父节点的关系:如果它是父节点的左孩子,那么,父节点就是它的后继。3,如果它是父节点的右孩子,那么我们可以向上倒推,直到某个节点(或者不存在这样的节点,返回空指针)是其父节点的左孩子。

Complexity

最坏情况下,考虑一棵树只有右孩子,而输入恰好是最右节点。在这个情况下,我们需要向上倒推遍历所有节点,此时复杂度O(n)。平均情况下,复杂度为O(h),h为树的高度。

Code

Node nextNode(Node node){
    if (node == null) return null;
    if (node.right != null) {
        return leftMostChild(node.right);
    } else {
        Node parent = node.parent;
        while (node == parent.right || parent == null){
            node = parent;
            parent = parent.parent;
        }
        return parent;
    }
}

Node leftMostChild(Node node){
    if (node == null){
        return null;
    }
    
    while( node.left != null){
        node = node.left;
    }
    return node;
}