【LeetCode 1305】All Elements in Two Binary Search Trees【Medium】【JAVA】

爱被打了一巴掌 2021-09-21 01:26 182阅读 0赞

## 1. 题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]  
题目链接：https://leetcode.com/problems/all-elements-in-two-binary-search-trees/

## 2. 题意 ##

题目要求是合并两个搜索二叉树，合并成为一个List

## 3. 方法 ##

### 3.1 思路 ###

比较简单的做法，由于两棵树都是二叉搜索树，通过中序遍历，输出有序的数组，再将两个数组进行合并，时间复杂度上为`O(n)`。

### 3.2 代码 ###

public List<Integer> getAllElements(TreeNode root1, TreeNode root2) { 
            List<Integer> list1 = new ArrayList<>();
            inorderTraversal(root1, list1);
    
            List<Integer> list2 = new ArrayList<>();
            inorderTraversal(root2, list2);
    
            List<Integer> list = new ArrayList<>();
            int i1 = 0, i2 = 0;
            while (i1 < list1.size() && i2 < list2.size()) { 
                if (list1.get(i1) > list2.get(i2)) { 
                    list.add(list2.get(i2++));
                } else { 
                    list.add(list1.get(i1++));
                }
            }
    
            while (i1 < list1.size()) { 
                list.add(list1.get(i1++));
            }
            while (i2 < list2.size()) { 
                list.add(list2.get(i2++));
            }
    
            return list;
        }
    
    	// 中序遍历
        private void inorderTraversal(TreeNode root, List<Integer> list) { 
            if (root == null) { 
                return;
            }
            inorderTraversal(root.left, list);
            list.add(root.val);
            inorderTraversal(root.right, list);
        }

### 3.3 运行结果 ###

![在这里插入图片描述][20191229163040735.png]

## 4. 相关链接 ##

[本题代码的github链接][github]  
[LeetCode Top 100 Liked Questions 题目][LeetCode Top 100 Liked Questions]  
[其他LeetCode题目][LeetCode]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/256dcd7665c747979ce71fced8571274.png
[20191229163040735.png]: /images/20210920/df3fe8c9c74f4ce6b17708b71558ccee.png
[github]: https://github.com/Parallelline1996/Leetcode/blob/master/Problems/src/main/java/page14/N1305_AllElementsInTwoBinarySearchTrees.java
[LeetCode Top 100 Liked Questions]: https://blog.csdn.net/applying/article/category/9466044
[LeetCode]: https://blog.csdn.net/applying/category_8110580.html