查找两个 BST 中和等于给定值 x 的对

2025年3月17日 | 阅读 12 分钟

问题陈述

给定两个 BST，分别有 x1 和 x2 个不同的节点，要求找出两个节点的值，使其和恰好等于给定值 x。

BST 1:
    3
   / \
  1   4
 /     \
0       2
BST 2:
    7
   / \
  5   10
 /     /\
4     8  12
Target value x = 10
Output:
3
The pairs are:
(3,7), (10,0), and (2,8)

同样尝试实现此方法的代码

方法 1

要在两个二叉搜索树（BST）中识别数对，您可以执行以下步骤，无需担心抄袭问题

对于 BST 1 中的每个节点值 'a'，执行搜索以在 BST 2 中查找值 '(x - a)'。
如果找到所需值，则增加计数以跟踪数对。

上述方法的 Java 实现

import java.util.*;
// Definition of a TreeNode, representing a node in a Binary Search Tree (BST).
class TreeNode {
    int value;
    TreeNode left, right;
    TreeNode(int x) {
        value = x;
        left = right = null;
    }
}
public class PairCounter {
    // Function to insert a node in a Binary Search Tree (BST).
    static TreeNode insert(TreeNode root, int value) {
        if (root == null)
            return new TreeNode(value);
        if (value < root.value)
            root.left = insert(root.left, value);
        else if (value > root.value)
            root.right = insert(root.right, value);
        return root;
    }
    // Function to count pairs with a sum equal to a target sum in two BSTs.
    static int countPairsWithSum(TreeNode root1, TreeNode root2, int targetSum) {
        // Create a set to store values from the second BST.
        Set<Integer> valueSet = new HashSet<>();      
        // Create a stack for iterative traversal of the second BST.
        Stack<TreeNode> stack = new Stack<>();       
        TreeNode current = root2;
        // Traverse the second BST and store values in the set.
        while (current != null || !stack.empty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            valueSet.add(current.value);
            current = current.right;
        }
        // Initialize a count to keep track of pairs with the target sum.
        int count = 0;
        current = root1;
        // Traverse the first BST and search for values that form pairs with the target sum.
        while (current != null || !stack.empty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();           
            // If (targetSum - current.value) is in the set, increment the count.
            if (valueSet.contains(targetSum - current.value))
                count++;      
            current = current.right;
        }
        return count;
    }
    public static void main(String[] args) {
        // Create two empty BSTs, root1 and root2.
        TreeNode root1 = null, root2 = null;     
        // Insert values into the first BST (root1).
        root1 = insert(root1, 5);
        root1 = insert(root1, 3);
        root1 = insert(root1, 7);
        root1 = insert(root1, 2);
        root1 = insert(root1, 4);
        root1 = insert(root1, 6);
        root1 = insert(root1, 8);
        // Insert values into the second BST (root2).
        root2 = insert(root2, 10);
        root2 = insert(root2, 6);
        root2 = insert(root2, 15);
        root2 = insert(root2, 3);
        root2 = insert(root2, 8);
        root2 = insert(root2, 11);
        root2 = insert(root2, 18);
        // Set the target sum for finding pairs.
        int targetSum = 16;
        // Count pairs with the specified target sum in the two BSTs.
        int count = countPairsWithSum(root1, root2, targetSum);
        // Print the count of pairs with the target sum.
        System.out.println("Count of pairs with sum " + targetSum + " is " + count);
    }
}

输出

Count pairs from two BSTs whose sum is equal to given value x

说明

插入方法

insert 方法用于将具有给定值的新节点插入 BST。它确保根据节点值将节点添加到适当的位置。

countPairsWithSum 方法

countPairsWithSum 方法以两个 BST（root1 和 root2）和一个目标和（targetSum）作为输入。
它使用一个集合（valueSet）来存储第二个 BST（root2）中的值，并使用一个栈（stack）进行迭代遍历。
该方法遍历 root2 并用其值填充 valueSet，为后续的数对计数做准备。
然后它初始化一个计数器来跟踪数对，并遍历 root1 以搜索与 valueSet 中的值组合形成目标和的数对。
如果找到一个数对，则计数器递增。

方法 2

从其最小值到最大值遍历第一个 BST (BST 1)。这可以通过迭代中序遍历完成，该遍历以升序访问节点。
同时，从其最大值到最小值遍历第二个 BST (BST 2)。这是通过反向中序遍历实现的，以降序访问节点。
在遍历两个 BST 的同时，在遍历的给定点处将 BST 1 和 BST 2 中相应节点的值相加。
如果这些节点值的和等于目标值 'x'，则增加计数以跟踪数对。
如果和小于 'x'，则移动到 BST 1 中当前节点的后继节点，以潜在地增加和。
如果和大于 'x'，则移动到 BST 2 中当前节点的前驱节点，以潜在地减少和。
继续这些操作，直到其中一个遍历完成。

该方法有效地在两个 BST 中找到和等于目标值 'x' 的节点对，是解决此问题的常用方法。

算法

将计数初始化为 0。
初始化两个空栈，stack1 用于 BST1，stack2 用于 BST2。
同时开始以升序遍历 BST1 并以降序遍历 BST2。
- 将 curr1 初始化为 BST1 中最左侧的节点（最小值节点）。
- 将 curr2 初始化为 BST2 中最右侧的节点（最大值节点）。
当 curr1 和 curr2 都不为 null 或当 stack1 和 stack2 都不为空时，执行以下操作
1. 以升序（中序）遍历 BST1 并将节点压入 stack1
  - 当 curr1 不为 null 时，将 curr1 压入 stack1，并将 curr1 更新为 curr1.left。
2. 以降序（反向中序）遍历 BST2 并将节点压入 stack2
  - 当 curr2 不为 null 时，将 curr2 压入 stack2，并将 curr2 更新为 curr2.right。
在循环中：
1. 如果 stack1 为空或 stack2 为空，则中断循环，因为其中一个遍历已完成。
2. 从 stack1 和 stack2 中弹出顶部节点（top1 和 top2）。
3. 计算和为 sum = top1.value + top2.value。
4. 如果 sum 等于 'x'
  - 将计数增加 1。
5. 如果 sum 小于 'x'
  - 移动到 BST1 中 top1 的中序后继节点
  - 将 curr1 设置为 top1.right。
6. 如果 sum 大于 'x'
  - 移动到 BST2 中 top2 的中序前驱节点
  - 将 curr2 设置为 top2.left。
返回计数，作为两个 BST 中和等于 'x' 的数对总数。
算法结束。

上述方法的 Java 实现

import java.util.Stack;

public class PairCounter {

    // Definition of TreeNode class for a binary tree node.
    static class TreeNode {
        int value;
        TreeNode left, right;
        public TreeNode(int value) {
            this.value = value;
            left = null;
            right = null;
        }
    }

    // Initialize two binary trees.
    static TreeNode tree1;
    static TreeNode tree2;
    // Function to count pairs of nodes from two binary trees with a sum equal to a given target.
    static int countPairsWithSum(TreeNode tree1, TreeNode tree2, int targetSum) {
        // If either of the binary trees is empty, there can be no pairs.
        if (tree1 == null || tree2 == null)
            return 0;
        // Initialize two stacks for inorder traversal of both binary trees.
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        TreeNode top1, top2;
        int count = 0;
        // The loop continues until either of the traversals completes.
        while (true) {
            // Inorder traversal of tree1.
            while (tree1 != null) {
                stack1.push(tree1);
                tree1 = tree1.left;
            }
            // Reverse inorder traversal of tree2.
            while (tree2 != null) {
 stack2.push(tree2);
                tree2 = tree2.right;
            }
            // If either of the stacks becomes empty, the traversal is complete.
            if (stack1.empty() || stack2.empty())
                break;
            // Peek the top nodes of both stacks.
            top1 = stack1.peek();
            top2 = stack2.peek();
            // Calculate the sum of values of the current nodes.
            int currentSum = top1.value + top2.value;
            // If the sum is equal to the target, increment the count and move to the next nodes.
            if (currentSum == targetSum) {
                count++;
                stack1.pop();
                stack2.pop();
                tree1 = top1.right;
                tree2 = top2.left;
            } 
// If the sum is less than the target, move to the next node in tree1.
            else if (currentSum < targetSum) {
                stack1.pop();
                tree1 = top1.right;
            } 
            // If the sum is greater than the target, move to the next node in tree2.
            else {
                stack2.pop();
                tree2 = top2.left;
            }
        }
        // Return the count of pairs with the specified target sum.
        return count;
    }
    public static void main(String args[]) {
        // Create the first binary tree (tree1).
        tree1 = new TreeNode(5);
        tree1.left = new TreeNode(3);
        tree1.right = new TreeNode(7);
        tree1.left.left = new TreeNode(2);
        tree1.left.right = new TreeNode(4);
        tree1.right.left = new TreeNode(6);
        tree1.right.right = new TreeNode(8);
        // Create the second binary tree (tree2).
        tree2 = new TreeNode(10);
        tree2.left = new TreeNode(6);
        tree2.right = new TreeNode(15);
        tree2.left.left = new TreeNode(3);
        tree2.left.right = new TreeNode(8);
        tree2.right.left = new TreeNode(11);
        tree2.right.right = new TreeNode(18);

        // Define the target sum.
        int targetSum = 16;
        // Call the countPairsWithSum function to count pairs with the target sum and print the result.
        System.out.println("Count of pairs with sum " + targetSum + " is " + countPairsWithSum(tree1, tree2, targetSum));
    }
}

输出

时间复杂度：O(n1+n2)

空间复杂度：O(h1+h2)

方法 3

利用递归策略解决此问题，即遍历 BST1，对于遇到的每个节点，计算 BST2 中的差值 (x - root1.data)，然后增加计数器以跟踪出现次数。

上述方法的 Java 实现

public class TwoBSTPairCount {
    // Definition of a TreeNode class to represent nodes in a binary search tree.
    static class TreeNode {
        int value;            // Value stored in the node.
        TreeNode left, right; // References to the left and right child nodes.
        public TreeNode(int value) {
            this.value = value;
            left = null;
            right = null;
        }
    }
    static TreeNode root1; // Root node of the first binary search tree (BST).
    static TreeNode root2; // Root node of the second binary search tree (BST).
    public static int pairCount = 0; // Counter to keep track of the number of pairs found.
    // Function to traverse both BSTs and count pairs whose sum is equal to the given 'sum'.
    public static void traverseAndCountPairs(TreeNode node1, TreeNode node2, int sum) {
        if (node1 == null || node2 == null) {
            return; // Base case: If either of the trees is empty, return.
        }
        // Recursively traverse the left and right subtrees of the first BST.
        traverseAndCountPairs(node1.left, node2, sum);
        traverseAndCountPairs(node1.right, node2, sum);
        int diff = sum - node1.value; // Calculate the difference needed to find a pair.
        findPairs(node2, diff); // Search for pairs in the second BST using the difference.
    }
    // Function to find pairs in the second BST that match the given difference.
    private static void findPairs(TreeNode node2, int diff) {
        if (node2 == null) {
            return; // Base case: If the second BST is empty, return.
        }
        // Recursively search for pairs in the second BST, based on the difference.
        if (diff > node2.value) {
            findPairs(node2.right, diff); // Explore the right subtree if diff is greater.
        } else {
            findPairs(node2.left, diff); // Explore the left subtree if diff is less or equal.
        }
        // If a pair is found (nodes with values that sum up to the difference), increment the pairCount.
        if (node2.value == diff) {
            pairCount++;
        }
    }
    // Function to count pairs whose sum is equal to the given 'sum'.
    public static int countPairs(TreeNode root1, TreeNode root2, int sum) {
        traverseAndCountPairs(root1, root2, sum); // Initiate the traversal and counting process.
        return pairCount; // Return the total count of pairs.
    }
    public static void main(String args[]) {
        // Create the first binary search tree (BST).
        root1 = new TreeNode(5);
        root1.left = new TreeNode(3);
        root1.right = new TreeNode(7);
        root1.left.left = new TreeNode(2);
        root1.left.right = new TreeNode(4);
        root1.right.left = new TreeNode(6);
        root1.right.right = new TreeNode(8);
        // Create the second binary search tree (BST).
        root2 = new TreeNode(10);
        root2.left = new TreeNode(6);
        root2.right = new TreeNode(15);
        root2.left.left = new TreeNode(3);
        root2.left.right = new TreeNode(8);
        root2.right.left = new TreeNode(11);
        root2.right.right = new TreeNode(18);
        int sum = 16;
        System.out.println("Pairs = " + countPairs(root1, root2, sum)); // Print the count of pairs with the given sum.
    }
}

输出

时间复杂度： 代码的时间复杂度为 O(n1 * n2)，因为它涉及到遍历 BST1 中的每个节点，并且对于每个节点，遍历 BST2 以确定是否存在与给定差值匹配的数对。

辅助空间： 辅助空间复杂度为 O(h1 + h2)，其中 h1 表示 BST1 的高度，h2 表示 BST2 的高度。此空间是递归遍历期间函数调用堆栈所需的，它随着相应树的高度而增加。

方法 4： 利用 BST 迭代器的概念

两个类 InorderSuccessorIterator 和 InorderPredecessorIterator，分别用于中序和反向中序行为

每个类将包含三个函数

hasNext： 只要遍历正在进行，就返回 true。

next： 将指针移动到下一个节点。

peek： 提供当前遍历中的当前节点。

在建立这两个类的两个实例后，当两个类都有下一个节点时执行迭代器。在每次迭代中计算总和。如果总和等于 x，则通过推进 iterator1 和 iterator2 的下一个指针来继续。如果总和大于 x，则递增 iterator2 的下一个指针；否则，当总和小于 x 时，递增 iterator1 的下一个指针。

上述方法的 Java 实现

import java.util.Stack;
// Definition of a TreeNode, representing a node in a Binary Search Tree (BST).
class TreeNode {
    int value;
    TreeNode left, right;
    // Constructor to initialize a TreeNode with a given value.
    public TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
// Iterator for traversing the in-order successor of a BST.
class InorderSuccessorIterator {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode root;
    boolean hasPeeked = false;
    // Constructor to initialize the iterator with a BST root.
    public InorderSuccessorIterator(TreeNode root) {
        this.root = root;
    }
    // Check if there is a next node in the in-order successor traversal.
    public boolean hasNext() {
        if (!stack.isEmpty() || root != null)
            return true;
        return false;
    }
    // Get the next node in the in-order successor traversal without moving the iterator.
    public TreeNode peek() {
        if (!hasNext())
            return null;
        while (root != null) {
            stack.push(root);
            root = root.left;
            hasPeeked = true;
        }
        return stack.peek();
    }
  // Move the iterator to the next node in the in-order successor traversal and return its value.
    public int next() {
        if (!hasNext())
            return -1;
        if (!hasPeeked)
            peek();
        hasPeeked = false;
        root = stack.pop();
        TreeNode temp = root;
        root = root.right;
        return temp.value;
    }
}
// Iterator for traversing the in-order predecessor of a BST.
class InorderPredecessorIterator {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode root;
    boolean hasPeeked = false;
    // Constructor to initialize the iterator with a BST root.
    public InorderPredecessorIterator(TreeNode root) {
        this.root = root;
    }
    // Check if there is a next node in the in-order predecessor traversal.
    public boolean hasNext() {
        if (!stack.isEmpty() || root != null)
            return true;
        return false;
    }
    // Get the next node in the in-order predecessor traversal without moving the iterator.
    public TreeNode peek() {
        if (!hasNext())
            return null;
        while (root != null) {
            stack.push(root);
            root = root.right;
            hasPeeked = true;
        }
        return stack.peek();
    }
    // Move the iterator to the next node in the in-order predecessor traversal and return its value.
    public int next() {
        if (!hasNext())
            return -1;
        if (!hasPeeked)
            peek();
        hasPeeked = false;
        root = stack.pop();
        TreeNode temp = root;
        root = root.left;
        return temp.value;
    }
}

// Class to count pairs with a given sum in two BSTs.
class PairCounter {
    // Function to count pairs with a sum equal to a target sum in two BSTs.
    public static int countPairs(TreeNode node1, TreeNode node2, int targetSum) {
        InorderSuccessorIterator iterator1 = new InorderSuccessorIterator(node1);
        InorderPredecessorIterator iterator2 = new InorderPredecessorIterator(node2);
        int count = 0;
        // Iterate through the iterators while there are nodes in both BSTs.
        while (iterator1.hasNext() && iterator2.hasNext()) {
            TreeNode current1 = iterator1.peek();
            TreeNode current2 = iterator2.peek();
            int sum = current1.value + current2.value;

            // Check the sum and update the iterators accordingly.
            if (sum == targetSum) {
                count++;
                iterator1.next();
                iterator2.next();
            } else if (sum > targetSum) {
                iterator2.next();
            } else {
                iterator1.next();
            }
        }
        return count;
    }
    // Main method to test the pair counting functionality.
    public static void main(String args[]) {
        TreeNode root1, root2;

        // Formation of BST 1
        root1 = new TreeNode(5);
        root1.left = new TreeNode(3);
        root1.right = new TreeNode(7);
        root1.left.left = new TreeNode(2);
        root1.left.right = new TreeNode(4);
        root1.right.left = new TreeNode(6);
        root1.right.right = new TreeNode(8);
        // Formation of BST 2
        root2 = new TreeNode(10);
        root2.left = new TreeNode(6);
        root2.right = new TreeNode(15);
        root2.left.left = new TreeNode(3);
        root2.left.right = new TreeNode(8);
        root2.right.left = new TreeNode(11);
        root2.right.right = new TreeNode(18);
        // Set the target sum for finding pairs.
        int targetSum = 16;
        // Count pairs with the specified target sum in the two BSTs.
        int count = countPairs(root1, root2, targetSum);
        // Print the count of pairs with the target sum.
        System.out.println("Count of pairs with sum " + targetSum + " is " + count);
    }
}

输出

时间复杂度： O(n1 + n2)，其中 n1 和 n2 分别是第一棵树和第二棵树中的节点总数。

辅助空间： O(h1 + h2)，其中 h1 表示第一棵树的高度，h2 表示第二棵树的高度。

下一个主题数据结构中的倒序对计数问题

查找两个 BST 中和等于给定值 x 的对

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

查找两个 BST 中和等于给定值 x 的对

相关帖子

查找范围 L 到 R 中大于 K 的元素数量 (离线查询)

获取二叉树中给定键的层级

用于范围顺序统计的归并排序树

最长公共子串

栈中入栈和出栈的区别

分配最少页数

B 树性质

数据结构中的结构体

链表交集

Burkhard Keller Tree (BK Tree)

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器