C++LeetCode 구현(103.이 진 트 리 의 자형 층 차 를 옮 겨 다 니 기)

[LeetCode]103.Binary Tree Zigzag Level Order Traversal 이 진 트 리 의 지그재그 층 차 를 옮 겨 다 닌 다.
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
    3
/ \
9  20
/  \
15   7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
이 두 갈래 나무의 지그재그 층 차 는 이전의 것 이다  Binary Tree Level Order Traversal  의 변형,다른 점 은 한 줄 은 왼쪽 에서 오른쪽으로 옮 겨 다 니 고 다음 줄 은 오른쪽 에서 왼쪽으로 옮 겨 다 니 며 교차 왕복 하 는 지그재그 의 층 차 를 옮 겨 다 니 는 것 이다.가장 간단 하고 직접적인 방법 은 층 차 를 옮 겨 다 니 며 하나의 변수 cnct 를 사용 하여 현재 의 층수(0 부터)를 통계 하고 모든 홀수 층 의 결점 값 을 뒤 집 으 면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> res;
        queue<TreeNode*> q{{root}};
        int cnt = 0;
        while (!q.empty()) {
            vector<int> oneLevel;
            for (int i = q.size(); i > 0; --i) {
                TreeNode *t = q.front(); q.pop();
                oneLevel.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            if (cnt % 2 == 1) reverse(oneLevel.begin(), oneLevel.end());
            res.push_back(oneLevel);
            ++cnt;
        }
        return res;
    }
};

우 리 는 위의 해법 을 최적화 시 킬 수 있다.배열 을 뒤 집 는 것 은 가능 하지만 시간 이 비교적 오래 걸린다.만약 에 모든 노드 값 이 배열 에 있 는 좌 표를 직접 계산 할 수 있다 면 직접 업 데 이 트 를 할 수 있다.각 층 의 결 점 수 는 알 고 있 기 때문에 대열 의 요소 갯 수 이기 때문에 배열 의 크기 를 직접 초기 화 할 수 있 습 니 다.이 때 하나의 변수 인 left ToRight 를 사용 하여 순 서 를 표시 합 니 다.처음에는 true 였 습 니 다.이 변수 가 true 일 때 배열 에 가입 할 때마다 위 치 는 i 자체 입 니 다.변수 가 false 이면 size-1-i 위치 에 가입 하면 배열 을 뒤 집 는 것 과 같 습 니 다.층 마다 옮 겨 다 니 면 뒤 집어 야 합 니 다. left ToRight 변 수 는 oneLevel 을 결과 res 에 추가 하 는 것 을 잊 지 마 세 요.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> res;
        queue<TreeNode*> q{{root}};
        bool leftToRight = true;
        while (!q.empty()) {
            int size = q.size();
            vector<int> oneLevel(size);
            for (int i = 0; i < size; ++i) {
                TreeNode *t = q.front(); q.pop();
                int idx = leftToRight ? i : (size - 1 - i);
                oneLevel[idx] = t->val;
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            leftToRight = !leftToRight;
            res.push_back(oneLevel);
        }
        return res;
    }
};

우 리 는 또한 재 귀적 인 방법 으로 풀 수 있 습 니 다.여 기 는 실제 적 으로 선착순 으로 옮 겨 다 니 는 것 입 니 다.재 귀적 함 수 는 하나의 변수 level 로 현재 의 깊이 를 기록 해 야 합 니 다.level 은 0 에서 시작 되 기 때문에 결과 res 의 크기 가 level 과 같다 면 결과 res 에 빈 집합 을 새로 추가 해 야 합 니 다.그러면 res[level]가 경 계 를 넘 지 않도록 보장 할 수 있 습 니 다.res[level]를 꺼 낸 후 levle 의 패 리 티 를 판단 합 니 다.짝수 라면 node->val 을 oneLevel 의 끝 에 넣 고 홀수 라면 oneLevel 의 시작 에 추가 합 니 다.그 다음 에 node 의 좌우 자 결점 에 대해 재 귀 함 수 를 호출 합 니 다.이때 level+1 에 들 어가 면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 3:

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        helper(root, 0, res);
        return res;
    }
    void helper(TreeNode* node, int level, vector<vector<int>>& res) {
        if (!node) return;
        if (res.size() <= level) {
            res.push_back({});
        }
        vector<int> &oneLevel = res[level];
        if (level % 2 == 0) oneLevel.push_back(node->val);
        else oneLevel.insert(oneLevel.begin(), node->val);
        helper(node->left, level + 1, res);
        helper(node->right, level + 1, res);
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/103
유사 한 제목:
Binary Tree Level Order Traversal
참고 자료:
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/discuss/33815/My-accepted-JAVA-solution
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/discuss/33825/c%2B%2B-5ms-version%3A-one-queue-and-without-reverse-operation-by-using-size-of-each-level
C++구현 LeetCode(103.이 진 트 리 의 지그재그 층 차 를 옮 겨 다 니 는 것)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++이 진 트 리 의 지그재그 층 차 를 옮 겨 다 니 는 내용 은 예전 의 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!