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

这道题到底在问什么

输入

root1=[50,30,70,20,40], root2=[60,45,80]

输出

[20,30,40,45,50,60,70,80]

最优解：一步一步想明白

1. 3记住「中序拿有序数组,再归并」,下面逐帧套它。
2. 4中序遍历 root1:它的左子树都走完了,现在轮到节点 20。
3. 5把 20 记进 A(变绿),接着去它的右子树。中序的顺序保证 A 一路都是升序。
4. 6中序遍历 root1:它的左子树都走完了,现在轮到节点 30。
5. 7把 30 记进 A(变绿),接着去它的右子树。中序的顺序保证 A 一路都是升序。
6. 8中序遍历 root1:它的左子树都走完了,现在轮到节点 40。
7. 9把 40 记进 A(变绿),接着去它的右子树。中序的顺序保证 A 一路都是升序。
8. 10中序遍历 root1:它的左子树都走完了,现在轮到节点 50。
9. 11把 50 记进 A(变绿),接着去它的右子树。中序的顺序保证 A 一路都是升序。
10. 12中序遍历 root1:它的左子树都走完了,现在轮到节点 70。
11. 13把 70 记进 A(变绿),接着去它的右子树。中序的顺序保证 A 一路都是升序。
12. 14root1 中序遍历完成,A = [20, 30, 40, 50, 70],已经是升序数组。
13. 15中序遍历 root2:它的左子树都走完了,现在轮到节点 45。
14. 16把 45 记进 B(变绿),接着去它的右子树。中序的顺序保证 B 一路都是升序。
15. 17中序遍历 root2:它的左子树都走完了,现在轮到节点 60。
16. 18把 60 记进 B(变绿),接着去它的右子树。中序的顺序保证 B 一路都是升序。
17. 19中序遍历 root2:它的左子树都走完了,现在轮到节点 80。
18. 20把 80 记进 B(变绿),接着去它的右子树。中序的顺序保证 B 一路都是升序。
19. 21root2 中序遍历完成,B = [45, 60, 80],已经是升序数组。
20. 22两个有序数组都拿到了。用双指针 i 扫 A、j 扫 B,每次比一比 A[i] 和 B[j],把较小的放进结果。
21. 23A[i]=20 ≤ B[j]=45,取 A 的 20(绿色),放进结果的第 1 位。
22. 24A[i]=30 ≤ B[j]=45,取 A 的 30(绿色),放进结果的第 2 位。
23. 25A[i]=40 ≤ B[j]=45,取 A 的 40(绿色),放进结果的第 3 位。
24. 26B[j]=45 < A[i]=50,取 B 的 45(绿色),放进结果的第 4 位。
25. 27A[i]=50 ≤ B[j]=60,取 A 的 50(绿色),放进结果的第 5 位。
26. 28B[j]=60 < A[i]=70,取 B 的 60(绿色),放进结果的第 6 位。
27. 29A[i]=70 ≤ B[j]=80,取 A 的 70(绿色),放进结果的第 7 位。
28. 30A 已取完,直接取 B 的 80(绿色),放进结果的第 8 位。
29. 31归并完成:最终升序结果 [20, 30, 40, 45, 50, 60, 70, 80]。回头看,靠 BST 中序天然有序,把树的问题化成了两个有序数组归并,时间 O(m+n)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
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 inorder(node, out):
            if not node:
                return
            inorder(node.left, out)
            out.append(node.val)
            inorder(node.right, out)
        a, b = [], []
        inorder(root1, a)
        inorder(root2, b)
        ans = []
        i = j = 0
        while i < len(a) or j < len(b):
            if j == len(b) or (i < len(a) and a[i] <= b[j]):
                ans.append(a[i]); i += 1
            else:
                ans.append(b[j]); j += 1
        return ans

#include <algorithm>
#include <climits>
#include <functional>
#include <iterator>
#include <numeric>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: vector<int> getAllElements(TreeNode* root1,TreeNode* root2){ vector<int>a,b,ans; function<void(TreeNode*,vector<int>&)> in=[&](TreeNode*n,vector<int>&v){ if(!n)return; in(n->left,v); v.push_back(n->val); in(n->right,v);}; in(root1,a); in(root2,b); merge(a.begin(),a.end(),b.begin(),b.end(),back_inserter(ans)); return ans; }};

import java.util.*;
class TreeNode{int val;TreeNode left,right;TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val,TreeNode left,TreeNode right){this.val=val;this.left=left;this.right=right;}}
class Solution{ public List<Integer> getAllElements(TreeNode root1,TreeNode root2){ ArrayList<Integer>a=new ArrayList<>(),b=new ArrayList<>(),ans=new ArrayList<>(); in(root1,a); in(root2,b); int i=0,j=0; while(i<a.size()||j<b.size()){ if(j==b.size()||(i<a.size()&&a.get(i)<=b.get(j)))ans.add(a.get(i++)); else ans.add(b.get(j++)); } return ans;} void in(TreeNode n,List<Integer>v){ if(n==null)return; in(n.left,v); v.add(n.val); in(n.right,v);} }

复杂度

面试官可能追问