java - 查找数字是否等于二叉搜索树中 2 个节点的总和

Question

这是我的代码。我正在遍历整棵树，然后在每个节点上进行查找。 find() 花费 O(log n)，因此整个程序花费 O(n log n) 时间。

有没有更好的方法来实现这个程序？我不仅在时间复杂度方面而且在一般情况下都在谈论更好。如何最好地实现它？

public boolean searchNum(BinTreeNode node, int num) {
    //validate the input

    if (node == null) {
        return false;
    }
    // terminal case for recursion

    int result = num - node.item;
    //I have a separate find() which finds if the key is in the tree
    if (find(result)) {
        return true;
    }
    return seachNum(node.leftChild, num) || searchNum(node.rightChilde, num);

}

public boolean find(int key) {

    BinTreeNode node = findHelper(key, root);
    if (node == null) {
        return false;
    } else {
        return true;
    }
}


private BinTreeNode findHelper(int key, BinTreeNode node) {
    if (node == null) {
        return null;
    }
    if (key == node.item) {
        return node;
    } else if (key < node.item) {
        return findHelper(key, node.leftChild);
    } else {
        return findHelper(key, node.rightChild);
    }
}

Answer 1

在二叉搜索树中查找两个节点总和为某个值的方法类似于在排序数组中查找总和为该值的两个元素。

在数组从小到大排序的情况下，您保留两个指针，一个从头开始，一个从尾开始。如果指针指向的两个元素之和大于target，则将右指针向左移动一位，如果和小于target，则将左指针向右移动一位。最终，两个指针要么指向总和为目标值的两个元素，要么在中间相遇。

boolean searchNumArray(int[] arr, int num) {
    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == num) {
          return true;
        } else if (sum > num) {
          right--;
        } else {
          left++;
        }
    }
    return false;
} 

如果对二叉搜索树进行中序遍历，它就变成了一个排序数组。因此，您可以将相同的想法应用到二叉搜索树上。

以下代码从两个方向进行迭代中序遍历。由于使用栈遍历，所以时间复杂度为O(n)，空间复杂度为O(h)，其中h为二叉树的高度。

class BinTreeIterator implements Iterator<BinTreeNode> {
    Stack<BinTreeNode> stack;
    boolean leftToRight;

    public boolean hasNext() {
        return !stack.empty();
    }

    public BinTreeNode next() {
        return stack.peek();
    }

    public void remove() {
        BinTreeNode node = stack.pop();
        if (leftToRight) {
            node = node.rightChild;
            while (node.rightChild != null) {
                stack.push(node);
                node = node.rightChild;
            }
        } else {
            node = node.leftChild;
            while (node.leftChild != null) {
                stack.push(node);
                node = node.leftChild;
            }
        }
    }

    public BinTreeIterator(BinTreeNode node, boolean leftToRight) {
        stack = new Stack<BinTreeNode>();
        this.leftChildToRight = leftToRight;

        if (leftToRight) {
            while (node != null) {
                stack.push(node);
                node = node.leftChild;
            }
        } else {
            while (node != null) {
                stack.push(node);
                node = node.rightChild;
            }
        }            
    }
}



public static boolean searchNumBinTree(BinTreeNode node, int num) {
    if (node == null)
        return false;

    BinTreeIterator leftIter = new BinTreeIterator(node, true);
    BinTreeIterator rightIter = new BinTreeIterator(node, false);

    while (leftIter.hasNext() && rightIter.hasNext()) {
        BinTreeNode left = leftIter.next();
        BinTreeNode right = rightIter.next();
        int sum = left.item + right.item;
        if (sum == num) {
            return true;
        } else if (sum > num) {
            rightIter.remove();
            if (!rightIter.hasNext() || rightIter.next() == left) {
                return false;
            }
        } else {
            leftIter.remove();
            if (!leftIter.hasNext() || leftIter.next() == right) {
                return false;
            }
        }
    }

    return false;
}