1305. 两棵二叉搜索树中的所有元素

曾经终败给现在 2022-12-21 06:19 76阅读 0赞

# 题目来源 #

1305. 两棵二叉搜索树中的所有元素

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 题目解析 #

> 关键在于合并两个有序数组

## 遍历 + 归并 ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
      private void dfs(TreeNode root, List<Integer> ansList) {
        
            if (root == null) {
        
                return;
            }
    
            dfs(root.left, ansList);
            ansList.add(root.val);
            dfs(root.right, ansList);
        }
    
        private List<Integer> merge(List<Integer> list1, List<Integer> list2) {
        
            List<Integer> ansList = new ArrayList<>();
            int size1 = list1.size();
            int size2 = list2.size();
            int index1, index2;
            for (index1 = 0, index2 = 0; index1 < size1 && index2 < size2;) {
        
                int num1 = list1.get(index1);
                int num2 = list2.get(index2);
                if (num1 < num2) {
        
                    ansList.add(num1);
                    index1++;
                } else {
        
                    ansList.add(num2);
                    index2++;
                }
            }
    
            while (index1 < size1) {
        
                ansList.add(list1.get(index1++));
            }
    
            while (index2 < size2) {
        
                ansList.add(list2.get(index2++));
            }
    
            return ansList;
        }
    
        public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        
            List<Integer> ansList1 = new ArrayList<>();
            List<Integer> ansList2 = new ArrayList<>();
            dfs(root1, ansList1);
            dfs(root2, ansList2);
    
            return merge(ansList1, ansList2);
        }
    
    }

复杂度分析  
时间复杂度：O(n) 两次的中序遍历和一次的归并操作都是O(n)O(n)的时间复杂度。  
空间复杂度：O(n).  
![在这里插入图片描述][2020111515263542.png_pic_center]

## 遍历 + 优先队列 ##

*  在树遍历的时候用一个优先队列（默认小根堆）来添加元素
 *  然后将优先队列的元素逐个取出加入list即可

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
    PriorityQueue<Integer> priorityQueue;
        public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        
             priorityQueue = new PriorityQueue<>();
             helper(root1);
             helper(root2);
    
            List<Integer> list = new ArrayList<>();
            
            while (!priorityQueue.isEmpty()){
        
                list.add(priorityQueue.poll());
            }
            return list;
        }
    
        private void helper(TreeNode root){
        
            if (root == null){
        
                return;
            }
    
            priorityQueue.add(root.val);
            helper(root.left);
            helper(root.right);
        }
    }

![在这里插入图片描述][20201115153441559.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/d02e5a2b47f84d3aac2d9c5a94e0fbe7.png
[2020111515263542.png_pic_center]: /images/20221120/5082ae0fd27c475692557704fde8df5b.png
[20201115153441559.png_pic_center]: /images/20221120/6fc311385223450ea12f3ebdbdcdf8b1.png