查找平衡 BST 中和为零的三个数

17 Mar 2025 | 4 分钟阅读

问题陈述

给定一棵平衡（高度平衡）的二叉搜索树，任务是找出是否存在和为 0 的三元组（3 个元素），如果存在则返回“存在”，否则返回“不存在”。

输入

	
		6
      /   \
  -13        14
	 \	    /  \
    -8     13   15
                /
               7

输出

{-13,  6, 7}

最直接的方法是检查二叉搜索树（BST）中的每个三元组，并验证它们的和是否等于零。此方法的时间复杂度为 O(n^3)。

一种改进的策略是生成一个辅助数组来存储二叉搜索树（BST）的中序遍历。由于 BST 的中序遍历始终产生排序的数据，因此该数组保证是有序的。

更好的方法

提供的解决方案在 O(n^2) 时间复杂度内运行，并利用 O(Logn) 的额外空间。

将给定的二叉搜索树（BST）转换为双向链表（DLL）。
遍历 DLL 的每个节点。如果节点的键为负数，则在 DLL 中搜索一对其和等于当前节点键的相反数的元素。

Java 实现

import java.util.*;
class BSTTriplets {
    // Definition for a Binary Search Tree (BST) node
    static class TreeNode {
intvalue;          // Value of the node
TreeNodeleft;      // Reference to the left child node
TreeNoderight;     // Reference to the right child node
    };

    static TreeNodehead;   // Head of the doubly linked list
    static TreeNodetail;   // Tail of the doubly linked list
    // Function to convert a Binary Search Tree (BST) to a Doubly Linked List (DLL)
    static void convertBSTtoDLL(TreeNode root) {
        // Base case: If the root is null, return
        if (root == null)
            return;
        // Recursively convert the left subtree
        if (root.left != null)
convertBSTtoDLL(root.left);
        // Set the left pointer of the current root to the current tail
root.left = tail;
        // If tail is not null, set the right pointer of tail to the current root,
        // else set the head to the current root
        if (tail != null)
            (tail).right = root;
        else
            head = root;
        // Update tail to the current root
        tail = root;
        // Recursively convert the right subtree
        if (root.right != null)
convertBSTtoDLL(root.right);
    }
    // Function to check if a given sum exists in the DLL
    static booleanisPresentInDLL(TreeNode head, TreeNode tail, int sum) {
        // Iterate through the DLL from both ends until head meets tail
        while (head != tail) {
int curr = head.value + tail.value;
            // If the sum is found, return true
            if (curr == sum)
                return true;
            // If the current sum is greater than the target, move tail to the left
            else if (curr > sum)
                tail = tail.left;
            // If the current sum is less than the target, move head to the right
            else
                head = head.right;
        }
        // If the sum is not found, return false
        return false;
    }
    // Function to check if there exists a triplet with sum equal to 0 in the BST
    static booleanisTripletPresent(TreeNode root) {
        // Check if the given BST is empty
        if (root == null)
            return false;
        // Initialize head and tail to null
        head = null;
        tail = null;
        // Convert the given BST to a doubly linked list
convertBSTtoDLL(root);
        // Iterate through the DLL and find a triplet with a sum of 0
        while ((head.right != tail) && (head.value< 0)) {
            // If a triplet is found, return true
            if (isPresentInDLL(head.right, tail, -1 * head.value))
                return true;
            // Move head to the right for the next iteration
            else
                head = head.right;
        }

        // If no triplet with a sum of 0 is found, return false
        return false;
    }
    // Function to create a new node with the given value
    static TreeNodecreateNewNode(intnum) {
TreeNode temp = new TreeNode();
temp.value = num;
temp.left = temp.right = null;
        return temp;
    }
    // Function to insert a value into the BST
    static TreeNodeinsert(TreeNode root, int value) {
        // If the root is null, create a new node with the given value
        if (root == null)
            return createNewNode(value);
        // If the value is less than the root's value, insert into the left subtree
        if (root.value> value)
root.left = insert(root.left, value);
        // If the value is greater than or equal to the root's value, insert into the right subtree
        else
root.right = insert(root.right, value);
        // Return the modified root
        return root;
    }
    // Main driver code
    public static void main(String[] args) {
TreeNode root = null;

        // Insert values into the BST
        root = insert(root, 6);
        root = insert(root, -13);
        root = insert(root, 14);
        root = insert(root, -8);
        root = insert(root, 15);
        root = insert(root, 13);
        root = insert(root, 7);
        // Check and print whether a triplet with sum 0 is present in the BST
        if (isTripletPresent(root))
System.out.print("Present");
        else
System.out.print("Not Present");
    }
}

输出

Find if there is a triplet in a balanced bst that adds to zero

时间复杂度：O(n^2)

空间复杂度： O(log(n))

下一个主题查找同时存在大写和小写的最大英文字母

← 上一个下一个 →

查找平衡 BST 中和为零的三个数

联系信息

关注我们

教程

面试题

在线编译器

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 中和为零的三个数

相关帖子

最大的全为 1 的子正方形

B 树插入

内部排序和外部排序的区别

从二叉搜索树中删除所有叶子节点

C 语言中的 AVL 树程序

经过恰好 K 步到达某个位置的方法数

二叉树应用

二进制链表的十进制等价物

和为给定值的子数组

查找最近的回文数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器