106일 (1305. All Elements in Two Binary Search Trees) recursion, tree

Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order.

 

Example 1:

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

Example 2:

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

 

Constraints:

• The number of nodes in each tree is in the range [0, 5000].
• -10^5 <= Node.val <= 10^5

 

- 접근방법

 

카테고리는 sorting으로 선택하였지만

실상은 전위순회 방식의 재귀함수를 이용한 후 list에 담고, list를 오름차순 정렬한 후 리턴하면 된다.

 

- 코드 

class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        ArrayList<Integer> list = new ArrayList<>();
        helper(root1, list);
        helper(root2, list);
        Collections.sort(list); // 정렬
        return list;
    }

    public void helper(TreeNode root, ArrayList<Integer> list){ // 전위순회
        if(root == null) return;

        list.add(root.val);
        helper(root.left,list);
        helper(root.right,list);
    }

}

재귀호출과 전위, 중위, 후위순회가 무엇인지 복습하는 문제이다.

 

 

 

 

https://leetcode.com/problems/all-elements-in-two-binary-search-trees/

All Elements in Two Binary Search Trees - LeetCode