如何在二叉搜索树中查找和为12的节点对，满足O(height)空间要求

你采用双栈分别模拟中序、逆中序遍历的方向是完全正确的，只需调整双指针的移动判断逻辑即可输出所有符合要求的节点对，具体实现逻辑如下：

• 两个栈的作用定义
  • 左栈：维护从小到大的中序遍历序列，每次弹出的元素是当前未访问过的最小节点
  • 右栈：维护从大到小的逆中序遍历序列，每次弹出的元素是当前未访问过的最大节点
• 初始化逻辑
  • 左栈先将根节点的所有左子节点依次压栈
  • 右栈先将根节点的所有右子节点依次压栈
  • 分别从两个栈弹出首元素作为左指针、右指针的初始值，同时将弹出节点的对应子树按规则压入栈
• 双指针遍历判断逻辑
  1. 计算左右指针指向节点的值的和，和目标值做对比：
     • 两者之和等于目标值：记录当前节点对，同时移动左指针取更大值、移动右指针取更小值
     • 两者之和小于目标值：需要更大的加数，仅移动左指针取更大值
     • 两者之和大于目标值：需要更小的加数，仅移动右指针取更小值
  2. 终止条件：左指针指向的节点值 >= 右指针指向的节点值，此时所有可能的节点对都已遍历完成

以你提供的示例、目标和为12的场景为例，遍历流程如下：

1. 初始左指针取2，右指针取10，和为12，记录(2,10)，移动左右指针
2. 左指针更新为5，右指针更新为7，和为12，记录(5,7)，移动左右指针
3. 左指针更新为7，右指针更新为5，此时左值大于右值，遍历终止，正好得到两组符合要求的节点对

核心实现代码（Python伪代码） #

# 左栈压入所有左子节点
def push_left(node, stack):
    while node:
        stack.append(node)
        node = node.left

# 右栈压入所有右子节点
def push_right(node, stack):
    while node:
        stack.append(node)
        node = node.right

def find_target_pairs(root, target):
    left_stack = []
    right_stack = []
    res = []
    # 初始化栈
    push_left(root, left_stack)
    push_right(root, right_stack)
    # 取初始左右指针
    left = left_stack.pop()
    push_left(left.right, left_stack)
    right = right_stack.pop()
    push_right(right.left, right_stack)

    while left.val < right.val:
        cur_sum = left.val + right.val
        if cur_sum == target:
            res.append((left.val, right.val))
            # 同时移动两个指针
            left = left_stack.pop()
            push_left(left.right, left_stack)
            right = right_stack.pop()
            push_right(right.left, right_stack)
        elif cur_sum < target:
            # 左指针右移，取更大值
            left = left_stack.pop()
            push_left(left.right, left_stack)
        else:
            # 右指针左移，取更小值
            right = right_stack.pop()
            push_right(right.left, right_stack)
    return res

该方案空间复杂度为O(height)，每个节点仅会被压栈、弹栈各一次，时间复杂度为O(nodes)，完全符合要求。

内容的提问来源于stack exchange，提问作者Dawson Smith