Leetcode 1305:两棵二叉搜索树中的所有元素(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1305:两棵二叉搜索树中的所有元素(超详细的解法!!!)

in leetcode with 0 comment

给你 root1root2 这两棵二叉搜索树。

请你返回一个列表,其中包含 两棵树 中的所有整数并按 升序 排序。

示例 1:

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

示例 2:

输入:root1 = [0,-10,10], root2 = [5,1,7,0,2]
输出:[-10,0,0,1,2,5,7,10]

示例 3:

输入:root1 = [], root2 = [5,1,7,0,2]
输出:[0,1,2,5,7]

示例 4:

输入:root1 = [0,-10,10], root2 = []
输出:[-10,0,10]

示例 5:

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

提示:

解题思路

最基本的想法就是层序遍历两颗树的所有节点,然后对所有节点元素排序输出即可。

class Solution:
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        q, res = [root1, root2], []
        
        while q:
            cur = q.pop(0)
            if cur:
                res.append(cur.val)
                q.append(cur.left)
                q.append(cur.right)
        return sorted(res)

但是这种做法显然不够优秀。我们没有利用二叉搜索树这个条件!我们可以通过中续遍历可以获得两个有序的队列,然后将两个队列元素合并,这样我们就不用排序了。参考Leetcode 88:合并两个有序数组(最详细解决方案!!!)

class Solution:
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        q1, q2, res = [], [], []
        
        def inOrder(root, q):
            if root:
                inOrder(root.left, q)
                q.append(root.val)
                inOrder(root.right, q)
        
        inOrder(root1, q1)
        inOrder(root2, q2)
        while q1 or q2:
            if not q1:
                res += q2
                break
            elif not q2:
                res += q1
                break
            else:
                res.append(q1.pop(0) if q1[0] < q2[0] else q2.pop(0))
        return res

python中,pythonsortTimSort,也就是归并排序的优化版本,所以最简洁的写法就是:

class Solution:
    def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        res = []
        
        def inOrder(root):
            if root:
                inOrder(root.left)
                res.append(root.val)
                inOrder(root.right)
        
        inOrder(root1)
        inOrder(root2)
        return sorted(res)

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses