1305-kir3i.md

1305. All Elements in Two Binary Search Trees

Solution

• 시간복잡도: O(N), N은 두 트리의 모든 노드 수 합

• 알고리즘

  트리 순회, 정렬

• 풀이설명

  1. 두 트리의 각 노드의 val을 오름차순으로 t1, t2에 저장합니다. 각 트리는 BST이므로 중위순회하면 오름차순으로 저장됩니다.
  2. t1과 t2의 값을 비교하여 작은 것부터 ans에 저장하면 자연스럽게 오름차순으로 정렬된 상태가 됩니다.

• 소스코드

  • C++

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        vector<int> ans, t1, t2;
        vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
            int i1=0, i2=0;
            popAscList(root1, t1);
            popAscList(root2, t2);
            
            while(i1<t1.size() && i2<t2.size()) {
                if (t1[i1] <= t2[i2])
                    ans.push_back(t1[i1++]);
                else
                    ans.push_back(t2[i2++]);
            }
            
            if (i1 == t1.size())
                ans.insert(ans.end(), t2.begin()+i2, t2.end());
            else
                ans.insert(ans.end(), t1.begin()+i1, t1.end());
            
            return ans;
        }
        
        void popAscList(TreeNode* root, vector<int> &t) {
            if (!root) {
                t = {};
                return;
            }
            
            if (root->left)
                popAscList(root->left, t);
            t.push_back(root->val);
            if (root->right)
                popAscList(root->right, t);
        }
    };

  • Python

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def getAllElements(self, root1, root2):
            ans = []
            t1 = []
            t2 = []
            self.popAscList(root1, t1)
            self.popAscList(root2, t2)
            
            i1 = i2 = 0
    
            while i1<len(t1) and i2<len(t2):
                if t1[i1] <= t2[i2]:
                    ans.append(t1[i1])
                    i1 += 1
                else:
                    ans.append(t2[i2])
                    i2 += 1
            if i1 == len(t1):
                ans.extend(t2[i2:])
            else:
                ans.extend(t1[i1:])
            return ans
        
        def popAscList(self, root, res):
            if not root:
                res = []
                return
            
            if root.left:
                self.popAscList(root.left, res)
            res.append(root.val)
            if root.right:
                self.popAscList(root.right, res)