107. Binary Tree Level Order Traversal II

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

Binary Tree Level Order Traversal II - LeetCode

 

이진 트리의 root가 주어졌을 때, level의 내림차순, 동일 level에서는 left에서 right 방향으로 2중 벡터에 담아 반환하는 문제다.

level의 오름차순을 dfs로 푸는 것까진 알겠는데 내림차순은... 생각이 안나서 reverse로 바꿔버림.

stl 사용을 생활화 합시다(?)

 

/**
 * 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:
    void solve(TreeNode* node, int level) {
        if (!node) {
            return;
        }
        
        if (v_.size() < level) {
            v_.push_back(vector<int>());
        }

        solve(node->left, level + 1);
        solve(node->right, level + 1);
        v_[level - 1].push_back(node->val);
    }
    
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        solve(root, 1);
        reverse(v_.begin(), v_.end());
        return v_;
    }
    
private:
    vector<vector<int>> v_;
};

 

 

 

이건 Discuss에 있는 정답 중 하나인데, 그냥 전체 tree 탐색하며 최대 레벨을 구하고 재탐색하는 방법이긴 한데.. reverse가 더 빠르지 않나 싶기도 하고..

int depth(TreeNode *root) {
    if (!root) return 0;
    return max(depth(root->left),depth(root->right))+1;
}

void levelOrder(vector<vector<int>> &ans, TreeNode *node, int level) {
    if (!node) return;
    ans[level].push_back(node->val);
    levelOrder(ans,node->left,level-1);
    levelOrder(ans,node->right,level-1);
}

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    int d = depth(root);
    vector<vector<int>> ans(d,vector<int> {});
    levelOrder(ans,root,d-1);
    return ans;
}