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

约 5 分钟
文章信息 2 个分类 5 个标签
分类
LeetCode 中等
标签
深度优先搜索 树 排序 二叉树 二叉搜索树

题目描述

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

题意分析

把两棵二叉搜索树中所有节点的值放到同一个列表，按非递减顺序返回。每个节点都要输出一次，相同值出现多次也必须全部保留。

任意一棵树可以为空，两棵都空时返回空列表。只需要有序的值列表，不需要合并成一棵新树，也不需要修改原来的父子连接。

解法：两次中序遍历加有序归并

核心思路

[!blue]

二叉搜索树的左侧值不大于根，右侧值不小于根。按左子树、根、右子树进行中序遍历，并在每棵子树内使用相同顺序，就会得到非递减序列。因此先分别生成两棵树的有序列表，再做归并，无需把所有值混在一起重新排序。

中序遍历用显式栈保存尚未访问的节点。先沿左孩子不断入栈，走到空位置后，栈顶就是下一次应访问的节点；弹出并记录它，再转向它的右子树，继续沿左链下降。待处理祖先仍在栈中，保证右子树处理完后还能回到正确位置。

两个有序列表分别用 i、j 指向尚未输出的第一个元素。每个指针所指的值都是自己列表剩余部分的最小值，所以全部剩余元素中的最小值必在这两个位置中；取较小者加入答案，并只推进对应指针，就能保持整体有序。

某一侧耗尽时，另一侧的剩余元素已经有序，可以继续依次输出。代码先检查右侧是否耗尽，再检查左侧存在且其值不大于右侧；借助短路判断，只有索引有效时才读取对应元素。

相等时先取任意一侧都正确，但每次只能消费实际输出的那一个节点值。另一侧相等值之后还会加入结果，从而保留重复次数。遍历和归并都让每个原节点恰好贡献一次，结束条件是两边全部耗尽。

解题步骤

  1. 用显式栈分别对两棵树中序遍历，得到两个有序列表。
  2. 将两个读取下标初始化为零。
  3. 两边都还有元素时，输出较小者并推进相应下标。
  4. 一边耗尽后继续输出另一边，直到两个列表全部处理完。
  5. 返回合成的有序结果。

代码实现

class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> a = inorder(root1);
        List<Integer> b = inorder(root2);
        List<Integer> answer = new ArrayList<>();
        int i = 0;
        int j = 0;

        while (i < a.size() || j < b.size()) {
            if (j == b.size() || i < a.size() && a.get(i) <= b.get(j)) {
                answer.add(a.get(i++));
            } else {
                answer.add(b.get(j++));
            }
        }

        return answer;
    }

    private List<Integer> inorder(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            values.add(root.val);
            root = root.right;
        }

        return values;
    }
}

func getAllElements(root1, root2 *TreeNode) []int {
    inorder := func(root *TreeNode) []int {
        values := []int{}
        stack := []*TreeNode{}
        for root != nil || len(stack) > 0 {
            for root != nil {
                stack = append(stack, root)
                root = root.Left
            }
            root = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            values = append(values, root.Val)
            root = root.Right
        }
        return values
    }
    a, b := inorder(root1), inorder(root2)
    answer := make([]int, 0, len(a)+len(b))
    i, j := 0, 0
    for i < len(a) || j < len(b) {
        if j == len(b) || i < len(a) && a[i] <= b[j] {
            answer = append(answer, a[i])
            i++
        } else {
            answer = append(answer, b[j])
            j++
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(n_1 + n_2)$，每个节点入栈、出栈、加入中序列表及归并输出都只发生一次。
  • 空间复杂度：$O(n_1 + n_2)$ 辅助空间，主要用于两个中序列表，遍历栈不超过相应树高；返回列表同样为线性规模。

关键点总结

[!green]

  • 利用搜索树性质先产生有序输入，再以线性归并组合。
  • 两个当前首值分别代表各自剩余部分的最小值，比较它们足以决定下一项。
  • 相等值不去重，空树与列表耗尽由同一套边界判断处理。

易错点总结

[!yellow]

  • 用集合保存结果，会丢掉相同值对应的多个节点。
  • 将中序遍历替换成层序遍历后直接归并，两个输入列表未必有序。
  • 比较元素前没有判断列表是否耗尽，空树或一侧提前结束时会越界。
  • 相等时两个下标一起前进却只输出一个值，会少保留一次出现。
  • 归并循环要求两侧都非空，结束后又没有处理剩余部分，会漏掉较长列表的尾部。
  • 弹出节点后忘记转向右子树，会漏掉它的右侧所有节点。

相似题目

题目 难度 关联与区别
88. 合并两个有序数组 简单 遍历结果转成两个有序数组后复用归并；本题新建列表，无需从尾部写入。
173. 二叉搜索树迭代器 中等 中序列表也可替换成两个受控迭代器，按需取得下一小值并减少预存数据。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/58852305
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！