99클럽 코테 스터디 8일차 TIL : 깊이/너비 우선탐색(DFS/BFS) - Reverse Odd Levels of Binary Tree

https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/

오늘문제는 그래도 간단했다!!

1시간 안에 풀기 성공 히히히

근데,, 딱히 효율적인 코드는 아닌것같다. 메모리사용량이나 실행속도가 그냥 평균에 머물러 있다.

뭔가 더 최적화할 방법이 있을것같긴한데,, 찾아보기도 귀찮고 시험기간이니까,,,,ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

---

처음에는 DFS를 이용해 노드 left, right 순서를 바꿔주도록 생각했다.

이렇게 하면 홀수 level은 의도대로 변경이 된다. (리버스로!)

근데 짝수 level도 같이 바뀌어 버리는 상황이 생긴다. 

그럼 바꿀 때 left, right 포인터를 바꾼다음, 짝수인 level은 그냥 val를 변경해주면 되는거 아닌가?? 싶었다.

근데!!!!!!! 이러면 비효율적이고 이렇게 해서 해결되지 않는다!

레벨이 깊어지면, 아래쪽은 냅다 뒤섞여버린다.

암튼 그래서 BFS로 풀었고, 그냥 odd level인 순간에는 stack을 이용해 val를 넣고, que에 node 포인터를 넣어준다.

그러면 stack에서 pop한건 반대로 나오고, que에서 pop한건 그대로 나오니까 val를 반대로 넣어줄 수 있다!

근데,,,,, 참 여러모로 비효율적인것같기도 하고 뭔가,, 뭔가 미묘하고 이상해서 좀 다른방법이 있을것같긴한데,,

/**
 * 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 dfs(TreeNode* node, int nowlevel){
        if(node == NULL){
            return;
        }
        if(nowlevel%2 == 0){ //지금이 짝수레벨
            TreeNode* leftnode = node->left;
            node->left = node->right;
            node->right = leftnode;
        }
        dfs(node->left, nowlevel+1);
        dfs(node->right, nowlevel+1);
    }
    TreeNode* reverseOddLevels(TreeNode* root) {
        
        
        queue<TreeNode*> que;
        queue<TreeNode*> oddque;
        stack<int> oddstack;
        
        que.push(root);
        int index = 0;
        int level = 0;
        
        while(que.size()>0){
            index++;
            level = (int)log2(index);
            //cout <<"level : "<<level<<endl;
            TreeNode* nownode = que.front();
            que.pop();
            
            if((level % 2) == 1){ // odd
                oddstack.push(nownode->val);
                oddque.push(nownode);
            }
            if(index == ((pow(2, level+1))-1)){ //last odd
                while(!oddstack.empty()){
                    TreeNode* oddnode = oddque.front();
                    oddque.pop();
                    oddnode->val = oddstack.top();
                    oddstack.pop();
                }
            }
            if(nownode->left != NULL){
                //cout<<"test"<<endl;
                que.push(nownode->left);
                que.push(nownode->right);
            }
            
        }
        
        return root;
        
            
    }
};

---

DFS로 풀는게 더 좋다고 해서 찾아봤다!

출처 : https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/discuss/2590808/JAVA-or-DFS-and-BFS

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        // We call the function from lvl 0, and everything starts from lvl 1
        traverse(root.left, root.right, 1);
        return root;
    }

    public void traverse(TreeNode node1, TreeNode node2, int lvl) {
        if (node1 == null || node2 == null) {
            return;
        }
        if (lvl % 2 == 1){
            int temp = node1.val;
            node1.val = node2.val;
            node2.val = temp;
        }

        traverse(node1.left, node2.right, lvl + 1);
        traverse(node1.right, node2.left, lvl + 1);
    }
}

// TC: O(n) -> Every node in the binary tree is visited
// SC: O(h) -> where h is the height of the binary tree

-> 나는 포인터를 바꾸어주었는데

그냥 값만 바꿔준다

그리고 traverse에 주는 left랑 right를 다르게준다!

저러면 각자 끝에 있는 노드들끼리 대칭으로 교환되므로, odd인 노드들만 번대순서가 된다!

대충 그려보면서 보니까 이해했당ㅋㅋㅋㅋㅋㅋㅋㅋ

DFS의 너무 이론적이고 한가지 방법만 알고있었던것같다,

이렇게 하는거구나,,,,,