[LeetCode 107108][간단] 두 갈래 트리의 차원 반복 II/질서수 그룹을 두 갈래 검색 트리로 변환

11507 단어 LeetCode#-간단하다
107, 두 갈래 나무의 차원 훑어보기 II 제목 링크
class Solution {
public:
    typedef pair<TreeNode *,int> pii;
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == NULL)return ans;
        queue<pii> mq;vector<int>p;
        mq.push(make_pair(root, 0));
        int d=0;
        while(!mq.empty()){
            pii q = mq.front();
            mq.pop();
            if(q.second != d){
                ans.emplace_back(p);
                d = q.second;
                p.clear();
            }
            p.emplace_back(q.first -> val);
            if(q.first->left)mq.push(make_pair(q.first->left, q.second + 1));
            if(q.first->right)mq.push(make_pair(q.first->right, q.second + 1));
        }
        if(p.size())ans.emplace_back(p);
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

108. 질서수 그룹을 두 갈래 검색 트리 제목으로 바꾸어 dfs 트리를 연결하고 비슷한 사상을 라인 트리에 나타낼 수 있다.
class Solution {
public:
    TreeNode *build(int l, int r, vector<int>& mv){
        if(r<l)return NULL;
        int m = (l + r) >> 1;
        TreeNode *root = new TreeNode(mv[m]);
        root->left = build(l, m-1, mv);
        root->right = build(m+1, r, mv);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(0,nums.size()-1, nums);
    }
};

좋은 웹페이지 즐겨찾기