【leetcode】1305. All Elements in Two Binary Search Trees

题目如下:

Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order.

Example 1:

【leetcode】1305. All Elements in Two Binary Search Trees

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]
Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]
Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []
Output: [-10,0,10]

Example 5:

【leetcode】1305. All Elements in Two Binary Search Trees

Input: root1 = [1,null,8], root2 = [8,1]
Output: [1,1,8,8] 

Constraints:

  • Each tree has at most 5000 nodes.
  • Each node's value is between [-10^5, 10^5].

解题思路:最简单的方法就是遍历两棵树,把值重新排序即可。

代码如下:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    res = []
    def recursive(self,node):
        self.res.append(node.val)
        if node.left != None:
            self.recursive(node.left)
        if node.right != None:
            self.recursive(node.right)
    def getAllElements(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: List[int]
        """
        self.res = []
        if root1 != None:
            self.recursive(root1)
        if root2 != None:
            self.recursive(root2)
        return sorted(self.res)

 

上一篇:剑指offer-判断树1中是否有树2,合并有序链表,旋转打印二维数组


下一篇:26、树的子结构