java - 树中大于 x 的最小元素

Question

如果我想找到树中大于元素 x 的最小元素，这是正确的方法吗？

class Node {
   int data;
   Node left, right;
}

Node root;

public Integer successorOf(int x) {
    return successorOf(x, root);
}

private Integer successorOf(int x, Node n) {
    if (n == null) {
        return null;
    }
    if (x < n.data) {
        Integer res = successorOf(x, n.left);
        if (res == null)
            res = n.data;
        return res;
    } else {
        return successorOf(x, n.right);
    }
}

我觉得这个解决方案没有检查整个树。

非常感谢您的帮助!

Answer 1

您可以使用中序遍历按升序获取元素，如果找到大于所需的元素，则您找到了答案

private int answer = -1;          // to store the answer

traverse(root,x,0)                // call this method

public void traverse(Node n,int x,int flag){

    if(n == null || flag == 1){   // flag=1 meaning we already found the answer
        return;
    }
    traverse(n.left,x,flag);
    if(n.data>x){                 // smallest value greater than x
        answer=n.data;            // store the answer 
        flag = 1;                 // mark flag = 1, to make subsequent calls 
    }                             // return from the function
    traverse(n.right,x,flag);

}