如何在不使用递归方法的情况下找到二叉搜索树的节点

Question

如果我有一个只将值作为参数（而不是节点）的方法，public Node finder (E val)我该如何找到相应的节点，而不管树的高度和宽度如何。如果该方法将 Node 作为参数，那么使用递归将是一个简单的解决方案。但不幸的是，我不允许更改方法签名。我怎样才能以聪明的方式做到这一点，而不是我在下面尝试的愚蠢的方式，这只会以大量的嵌入式if功能结束

public class BinarySearchTree<E extends Comparable<E>> {
    class Node {
        E value;
        Node leftChild = null;
        Node rightChild = null;
        Node(E value) {
            this.value = value;
        }
    }

    public Node finder(E val) {
        
        if (val == null) return null;
        if (root == null) return null;
        
        boolean flag = false;  
        Node temp = root;
        
        //find if Root Node matches value
        if(temp.value.compareTo(val) == 0) {
            flag = true;
            return temp;
        } 
        //if value is less than root check the left branch
        else if (temp.value.compareTo(val) > 0) {
            
            if(temp.leftChild.value.compareTo(val) == 0) {
                flag = true;
                return temp.leftChild;
            } 
            //more if statements here
        } 
        //if value is more than root check the right branch 
        else {
            if(temp.rightChild.value.compareTo(val) == 0) {
                flag = true;
                return temp.rightChild;
            }
            
            //more if statements here
        }
        
        return null;
    }
}

Answer 1

二叉搜索树有一个有趣的特性：

• 节点的左子树仅包含值小于节点值的节点。
• 节点的右子树只包含值大于节点键的节点。

假设您的类BinarySearchTree持有对根的引用，您可以迭代地遍历二叉树，直到到达该值或到达叶节点，这意味着您的值不存在于二叉搜索树中。这个搜索操作的时间复杂度是 O(log(n))。

这是一些伪代码

Find-Node(val):

    node = root
    while node != null:
      if val == node.val then return root
      if val < node.val then node = node.left
      if val > node.val then node = node.right

    return null