What is the optimal approach for merging two BSTs?

The optimal approach involves performing in-order traversal on both trees and merging them using the two-pointer technique.

How do I ensure the merged result is sorted?

In-order traversal ensures that elements from both trees are extracted in sorted order. Merging two sorted lists further maintains this order.

What if one of the trees is empty?

If one of the trees is empty, simply return the in-order traversal of the non-empty tree.

Can I solve this problem without recursion?

Yes, iterative solutions using a stack or a queue can replace recursion for DFS-based tree traversal.

How does this problem relate to binary-tree traversal?

This problem relies heavily on tree traversal techniques like in-order traversal to efficiently extract and merge elements from two binary search trees.

#1305

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

两棵二叉搜索树中的所有元素

给你 root1 和 root2 这两棵二叉搜索树。请你返回一个列表，其中包含两棵树中的所有整数并按升序排序。. 示例 1：输入： root1 = [2,1,4], root2 = [1,0,3] 输出： [0,1,1,2,3,4] 示例 2：输入： root1 = [1,null,8]…

树深度优先搜索二叉搜索树排序二叉树

题目描述

给你 root1 和 root2 这两棵二叉搜索树。请你返回一个列表，其中包含 两棵树 中的所有整数并按升序排序。.

示例 1：

输入：root1 = [2,1,4], root2 = [1,0,3]
输出：[0,1,1,2,3,4]

示例 2：

输入：root1 = [1,null,8], root2 = [8,1]
输出：[1,1,8,8]

提示：

每棵树的节点数在 [0, 5000] 范围内
-10⁵ <= Node.val <= 10⁵

lightbulb

解题思路

方法一：DFS + 归并

由于两棵树都是二叉搜索树，所以我们可以通过中序遍历得到两棵树的节点值序列 $\textit{a}$ 和 $\textit{b}$ ，然后使用双指针归并两个有序数组，得到最终的答案。

时间复杂度 $O(n+m)$ ，空间复杂度 $O(n+m)$ 。其中 $n$ 和 $m$ 分别是两棵树的节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getAllElements(
        self, root1: Optional[TreeNode], root2: Optional[TreeNode]
    ) -> List[int]:
        def dfs(root: Optional[TreeNode], nums: List[int]) -> int:
            if root is None:
                return
            dfs(root.left, nums)
            nums.append(root.val)
            dfs(root.right, nums)

        a, b = [], []
        dfs(root1, a)
        dfs(root2, b)
        m, n = len(a), len(b)
        i = j = 0
        ans = []
        while i < m and j < n:
            if a[i] <= b[j]:
                ans.append(a[i])
                i += 1
            else:
                ans.append(b[j])
                j += 1
        while i < m:
            ans.append(a[i])
            i += 1
        while j < n:
            ans.append(b[j])
            j += 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently merge two sorted lists using a two-pointer technique?
question_mark
Does the candidate understand the trade-offs between DFS and iterative approaches?
question_mark
How well does the candidate handle recursion or stack-based tree traversal methods?

warning

常见陷阱

外企场景

error
Not using in-order traversal, which results in an unnecessary sort step at the end.
error
Ignoring the fact that both trees are already sorted, leading to inefficient solutions.
error
Overcomplicating the solution by not merging the two trees while traversing.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if one of the trees is empty?
arrow_right_alt
How would the solution change if the trees were not binary search trees?
arrow_right_alt
Can the problem be solved without using extra space?

help

常见问题

外企场景

继续练习

#1373 二叉搜索子树的最大键值和 #1382 将二叉搜索树变平衡 #1038 从二叉搜索树到更大和树