查找数字是否等于二叉搜索树中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

在二进制搜索树中求和两个节点总和为某个值可以通过在排序数组中找到两个元素的相似方式来完成,该元素总和为该值.

在从小到大排序的数组的情况下,你保留两个指针,一个从开始开始,一个从结束开始.如果指针指向的两个元素的总和大于目标,则将右指针向左移动一个,如果总和小于目标,则将左指针向右移动一个.最终,两个指针将指向两个总和为目标值的元素,或者在中间相遇.

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);
    BinTreeIterator rightIter = new BinTreeIterator(node);

    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;
}