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

**文章首段摘要：** leetcode 上的「两个二叉搜索树中的所有元素」问题，求解时通常采用递归的方法，通过对两棵树同时进行中序遍历，并将结果合并到一个数组中。然而，这种方法需要额外的数组来存储结果，并且在最后需要对合并后的数组进行排序。本文提供了一种替代方法，通过同时遍历两棵树并直接按排序顺序填充答案数组，避免了额外的数组和排序步骤。

我在leetcode上为两个二叉搜索树中的所有元素问题编写了代码： https://leetcode.com/problems/all-elements-in-two-binary-search-trees/

我找不到其他人尝试以这种方式解决这个问题。我知道可以使用 helper() 函数改进此代码，但主要问题是排序，是否有一些优雅的方法可以在同时遍历两棵树时避免它？请参见 sort.ints(curr) 行。

我正在寻找一种同时遍历两棵树并直接按排序顺序填充答案数组的方法，无需额外的数组。

func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
    if root1 == nil && root2 == nil {
        return []int{}
    } else if root1 != nil && root2 != nil {
        curr := getAllElements(root1.Left, root2.Left)
        if root1.Val < root2.Val {
            curr = append(curr, root1.Val)
            curr = append(curr, root2.Val)
        } else {
            curr = append(curr, root2.Val)
            curr = append(curr, root1.Val)
        }
        curr = append(curr, getAllElements(root1.Right, root2.Right)...)
        sort.Ints(curr) //no TLE, but how to walk both trees at the same time, like in this code, to avoid this sorting?
        return curr
    } else if root1 != nil {
        curr := getAllElements(root1.Left, nil)
        curr = append(curr, root1.Val)
        curr = append(curr, getAllElements(root1.Right, nil)...)
        return curr
    } else if root2 != nil {
        curr := getAllElements(nil, root2.Left)
        curr = append(curr, root2.Val)
        curr = append(curr, getAllElements(nil, root2.Right)...)
        return curr
    }
    return []int{}
}

正确答案

这是1305 的解决方案。两个二叉搜索树中的所有元素

func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
    if root1 == nil && root2 == nil {
        return nil
    }
    var list1 []int
    if root1 != nil {
        list1 = inOrder(root1, list1)
    }
    
    var list2 []int
    if root2 != nil {
        list2 = inOrder(root2, list2)
    }
    
    if len(list1) == 0 {
        return list2
    }
    if len(list2) == 0 {
        return list1
    }
    
    var list3 []int
    for i, j := 0, 0;; {
        var elem1 int
        if len(list1) > i {
            elem1 = list1[i]
        } else {
            // we add the remaining elements from list2 into list3
            // there are no elements in list1
            if len(list2) > j {
                list3 = append(list3, list2[j:]...)
                break
            }
        }
        
        var elem2 int
        if len(list2) > j {
            elem2 = list2[j]
        } else {
            // we add the remaining elements from list1 into list3 
            // there are no elements in list2
            if len(list1) > i {
                list3 = append(list3, list1[i:]...)
                break
            }
        }
        
        if elem1 < elem2 {
            list3 = append(list3, elem1)
            i++
        } else {
            list3 = append(list3, elem2)
            j++
        }
    }
    return list3
}

func inOrder(node *TreeNode, list []int) []int {
    if node.Left != nil {
        list = inOrder(node.Left, list)
    }
    list = append(list, node.Val)
    if node.Right != nil {
        return inOrder(node.Right, list)
    }
    return list
}

今天带大家了解了的相关知识，希望对你有所帮助；关于Golang的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~