LeetCode653. Two Sum IV - Input is a BST_长安系列①小乔bst-CSDN博客

本文链接：https://blog.csdn.net/Yaokai_AssultMaster/article/details/78158333

本文介绍了一种高效算法，在二叉搜索树(BST)中寻找两个节点，使它们的值之和等于特定的目标值k。通过利用BST的有序特性，采用双指针策略从树的两端开始搜索，逐步逼近目标值。该算法的时间复杂度为O(n)，空间复杂度为O(log n)。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

The simplest solution for this question is probably get all the value out into an array and solve it just like a normal 2Sum.

However, since we are considering a BST, it would be more efficient to utilize the ordered feature of a BST.

The basic idea is the same like 2Sum, we start from the 2 sides of the numbers, in this case, the 2 sides would be the leftmost TreeNode and the rightmost TreeNode. And during checking the sum of 2 nodes, we have 3 possible conditions:

current sum == k, this is what we want, return true.
current sum < k, this means that we have to move the left node. In the case of BST, this indicates that we have to find the next greater node, which is the leftmost node in current node’s right subtree.
current sum > k, this means that we have to move the right node. In the case of BST, this indicates that we have to find the next smaller node in the tree, which is the rightmost node in current node’s left subtree.

During traversal, we have to keep the parent status of the nodes. Utilized the classic way — Deque/Stack.

A tricky point of this idea is how do we decide the stop point. Since there is no redundant values in the tree, we can use left.val == right.val to indicates that we have searched every node in the tree since now the pointers have met each other.

Assume n is the number of nodes in the BST, time complexity is O(n) since we visited each node in the tree. Space complexity is O(logn) on average since we keeps a Deque of the same hight with the tree, which is logn.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }

        // Use Deque as Stack
        Deque<TreeNode> leftSide = new ArrayDeque<>();
        Deque<TreeNode> rightSide = new ArrayDeque<>();

        // Find the greatest and smallest Node in the Tree first.
        TreeNode tmp = root;
        while (tmp != null) {
            leftSide.push(tmp);
            tmp = tmp.left;
        }
        tmp = root;
        while (tmp != null) {
            rightSide.push(tmp);
            tmp = tmp.right;
        }

        // Then perform the same 2 pointer idea like we are facing a sorted list
        // However, in this case, we always try to traverse the tree to looking
        // for the next smaller or larger TreeNode. This is applicable since 
        // this is a BST.
        TreeNode left = leftSide.pop();
        TreeNode right = rightSide.pop();

        while (left.val != right.val) {
            // If there is no redundant number in the Tree, 
            // then left.val == right.val can indicates a thorough search is completed.
            int currSum = left.val + right.val;
            if (currSum == k) {
                return true;
            } else if (currSum < k) {
                if (left.right != null) {
                    left = left.right;
                    while (left != null) {
                        leftSide.push(left);
                        left = left.left;
                    }
                }
                left = leftSide.pop();
            } else { // currSum > k
                if (right.left != null) {
                    right = right.left;
                    while (right != null) {
                        rightSide.push(right);
                        right = right.right;
                    }
                }
                right = rightSide.pop();
            }
        }

        return false;
    }
}