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

0x00 题目

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

0x01 思路

二叉搜索树​​中序遍历​​​是一个升序数组
得到 ​​​2​​​ 个升序数组后
再通过​​​比较​​​大小
把结果添加到​​​新​​数组中

0x02 解法

语言：​​Swift​​

树节点：​​TreeNode​​

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

解法：

func getAllElements(_ root1: TreeNode?, _ root2: TreeNode?) -> [Int] {
    var arr1: [Int] = []
    var arr2: [Int] = []
    
    // 中序遍历
    func inorder(_ root: TreeNode?, _ arr: inout [Int]) {
        guard let r = root else { return }
        
        inorder(r.left, &arr)
        arr.append(r.val)
        inorder(r.right, &arr)
    }
    
    // 得到 2 个升序数组
    inorder(root1, &arr1)
    inorder(root2, &arr2)
    
    // 比较大小，放入新数组
    var c1 = 0, c2 = 0
    var arr: [Int] = []
    while c1 < arr1.count && c2 < arr2.count {
        if arr1[c1] < arr2[c2] {
            arr.append(arr1[c1])
            c1 += 1
        }else{
            arr.append(arr2[c2])
            c2 += 1
        }
    }
    
    // 数组1 还有元素
    while c1 < arr1.count {
        arr.append(arr1[c1])
        c1 += 1
    }
    
    // 数组2 还有元素    
    while c2 < arr2.count {
        arr.append(arr2[c2])
        c2 += 1
    }
    
    return arr
}

0x03 我的小作品

欢迎体验我的作品之一：​​小编辑器-XCompiler​​​ 在线编辑器，包含多种语言，多达 20 种
​​App Store​​ 搜索即可~