La clase TreeNode se define solo con los elementos secundarios izquierdo y derecho.

public class TreeNode {

    public int val;
    public TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
    }
}

Mi código encuentra el siguiente nodo más bajo en O (n). Me preguntaba si es posible encontrarlo en lg (N) dado que el nodo no tiene un puntero a su nodo padre.

// run time O(n)
    public static Integer findNextLowest(TreeNode root, int target) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || stack.size() > 0) {

            while (cur != null) {
                stack.push(cur);
                cur = cur.right;
            }
            TreeNode node = stack.pop();
            if (node.val < target) return node.val; // found the next lowest
            cur = node.left;
        }
        return null;
    }
0
TonyGW 25 may. 2017 a las 18:39

2 respuestas

La mejor respuesta
private static TreeNode findNextLowest(TreeNode root, int target){
    TreeNode node = root;
    TreeNode res = null;
    while(node != null){
        while(node != null && node.val >= target){
            node = node.left;
        }
        while(node != null && node.val < target){
            res = node;
            node = node.right;
        }
    }
    return res;
}
1
Protocol 26 may. 2017 a las 19:08

No, porque no ha implementado un B binario earth T ree, solo un árbol binario.

Un BST limitará sus valores de modo que left.val <val <right.val, por lo que puede hacer

// run time O(log(n)) if cur is balanced
public static Integer findNextLowest(TreeNode cur, int target) {        
    if (target < cur.val) { return cur.left != null ? findNextLowest(cur.left, target) : null; }
    if (curr.right != null)
    { 
        Integer result = findNextLowest(cur.right, target);
        if (result != null) { return result; }
    }
    return cur.val;
}

Debe usar algo como un árbol R-B para asegurarse de que esté equilibrado

-1
Caleth 25 may. 2017 a las 20:24