[LeetCode] 1305. All Elements in Two Binary Search Trees - 문제 풀이

Description

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

Solution 1. 중위순회(Inorder)+병합(merge)

public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
    List<Integer> sortedList1 = new ArrayList<>();
    List<Integer> sortedList2 = new ArrayList<>();
    // inorder-traversal
    inOrder(root1,sortedList1);
    inOrder(root2,sortedList2);

    // merge 2 sortedList
    List<Integer> result = new ArrayList<>();
    int idx1 = 0;
    int idx2 = 0;
    while(idx1 < sortedList1.size() && idx2 < sortedList2.size() ){ //둘다 유효할 때만 반
        if(sortedList1.get(idx1) <= sortedList2.get(idx2)){
            result.add(sortedList1.get(idx1++));
        }else{
            result.add(sortedList2.get(idx2++));
        }
    }
    while(idx1 < sortedList1.size()) result.add(sortedList1.get(idx1++));
    while(idx2 < sortedList2.size()) result.add(sortedList2.get(idx2++));

    return result;
}

private void inOrder(TreeNode tree, List<Integer> result){ // 중위순회 left root right
    if(tree == null) return;
    inOrder(tree.left,result);
    result.add(tree.val);
    inOrder(tree.right,result);
}

각각의 트리를 중위순회(inorder-traversal)하여 두개의 정렬된 리스트를 만든 뒤 두 리스트를 머지해 줍니다.

Reference

All Elements in Two Binary Search Trees - LeetCode