Populating Next Right Pointers in Each Node

2021. 6. 25. 18:18· 자료구조 알고리즘/코딩테스트
목차
  1. 116. Populating Next Right Pointers in Each Node

116. Populating Next Right Pointers in Each Node

language: C++

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        
        // return connect1(root);
        
        return connect2(root);
    }
    
    Node* connect2(Node* root) {
        if (root == nullptr)
            return root;
        
        Node* value;
        queue<Node*> q;
        
        q.push(root);
        
        int size = 0;
        while (!q.empty()) {
            size = q.size();
            
            for (int i = 0; i < size; i++) {
                value = q.front();
                q.pop();
                
                if (i < size - 1)
                    value->next = q.front();
                
                if (value->left)
                    q.push(value->left);
                if (value->right)
                    q.push(value->right);
            }
        }
        
        return root;
    }
    
    Node* connect1(Node* root) {
        if (root == nullptr)
            return root;
        
        Node* leftmost = root;
        
        while(leftmost->left != nullptr) {
            Node* head = leftmost;
            
            while (head != nullptr) {
                head->left->next = head->right;
                
                if (head->next != nullptr) {
                    head->right->next = head->next->left;
                }
                
                head = head->next;
            }
            
            leftmost = leftmost->left;
        }
        
        return root;
    }
    
    
};

 

시도

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        return helper(root);
    }
    
    Node* helper(Node* root) {
        Node* value;
        Node* prevNode = nullptr;
        int idx = 0;
        queue<Node*> q;
        q.push(root);
        
        while(!q.empty()) {
            value = q.front();
            q.pop();
            if (prevNode != nullptr && prevNode->val != value->val)
                value->next = prevNode;
            
            if (value->left)
                q.push(value->left);
            if (value->right)
                q.push(value->right);
            
            prevNode = value->left;
        }
        
        return root;
    }
    
};

이러면 right child 만 안나온다

fail test case

Your input : [1,2,3,4,5,6,7]

Output : [1,#,2,#,4,6,#]

Expected : [1,#,2,3,#,4,5,6,7,#]

그래서 조금 고쳤는데

class Solution {
public:
    Node* connect(Node* root) {
        return helper(root);
    }
    
    Node* helper(Node* root) {
        Node* value;
        Node* valueTemp;
        Node* prevNode = nullptr;
        queue<Node*> qTemp;
        queue<Node*> q;
        q.push(root);
        qTemp.push(nullptr);
        
        while(!q.empty()) {
            value = q.front();
            q.pop();
            
            //if (prevNode != nullptr && prevNode->val != value->val)
            //    value->next = prevNode;
            
            if (value->left) {
                q.push(value->left);
                qTemp.push(value->left);
            }
            if (value->right) {
                q.push(value->right);
                qTemp.push(value->right);
                qTemp.push(nullptr);
            }
            
            // if (prevNode->val != value->val)
            //    prevNode = value->left;
            valueTemp = qTemp.front();
            qTemp.pop();
            value->next = valueTemp;
            if (valueTemp != nullptr && valueTemp->val == value->val) {
                valueTemp = qTemp.front();
                qTemp.pop();
                value->next = valueTemp;
            }
        }
        
        return root;
    }
    
};

Your input : [1,2,3,4,5,6,7]

Output : [1,#,2,3,#,4,5,#]

Expected : [1,#,2,3,#,4,5,6,7,#]

조금만 고쳐졌다..;

class Solution {
public:
    Node* connect(Node* root) {
        return helper(root);
    }
    
    Node* helper(Node* root) {
        Node* value;
        Node* valueTemp;
        // Node* prevNode = nullptr;
        queue<Node*> qTemp;
        queue<Node*> q;
        int level = 0;
        
        q.push(root);
        qTemp.push(nullptr);
        
        while(!q.empty()) {
            value = q.front();
            q.pop();
            
            //if (prevNode != nullptr && prevNode->val != value->val)
            //    value->next = prevNode;
            
            if (value->left) {
                q.push(value->left);
                qTemp.push(value->left);
            }
            if (value->right) {
                q.push(value->right);
                qTemp.push(value->right);
                qTemp.push(nullptr);
            }
            if (value->left || value->right)
                level++;
            
            // if (prevNode->val != value->val)
            //    prevNode = value->left;
            valueTemp = qTemp.front();
            qTemp.pop();
            value->next = valueTemp;
            if (valueTemp != nullptr && valueTemp->val == value->val) {
                valueTemp = qTemp.front();
                qTemp.pop();
                value->next = valueTemp;
            }
            
            if (value->next == nullptr) {
                level--;
            }
            
            if (value->next == nullptr && level > 1) {
                valueTemp = qTemp.front();
                qTemp.pop();
                value->next = valueTemp;
            }
            
            /*
            if (qTemp.size() > 1) {
                valueTemp = qTemp.front();
                qTemp.pop();
                value->next = valueTemp;
            }
            */
        }
        
        return root;
    }
    
};

현재 레벨을 가지고 어떻게 해보려고 했는데 항상 5 다음이 문제였다;

노드의 level 에 따라서 nullptr 을 만났을 때 면제권? 한 번 더 qTemp 의 다음으로 가리키도록 하는 것을 줘야겠다고 생각이 들었는데,

그러면 각 노드마다 자신의 level 을 기록해놔야하는데 더 쉬운 방법이 없을까 생각했었다. 시간 많이 지나서 걍 솔루션 고고

문제점

와 솔루션보고 그래도 생각하는 게 조금 는 게 느껴졌다? 

일단 처음 문제 보고 아 level order traversal 이구나 알아서 queue 를 써야겠네? 생각하고 -> 1학기에 자료구조를 들었으니까... 기억력;

전 노드를 저장해 놓고 그 다음 노드에서 그 전 노드를 저장하면 되는 거 아닌가? 생각하다가 

현재 노드에서 다음 노드를 저장해놓으면 되는 거 아닌가? 큐에 있을텐데.. 생각도 하고

level 을 사용하면 될 것 같은데? 근데 이러면 다시 다 저장해야되는 거 아니야? 생각했다

솔루션 보니까 두 가지 방법이 있었는데 하 생각했던 거 있어서 진짜 이렇게라도 조금이나마 나를 칭찬하면서 참고했다..

1) leftmost 를 두고 사용하며, 현재 노드에 연결시키는 방법

leftmost 노드를 저장해놓고, head를 두고, head 에서 

leftmost.left != nullptr 로 멈추는 조건을 걸어놓고 

2) level 을 가지고 하는 방법

level을 가지고 해야겠다는 생각은 했었는데 다시 다른 자료구조에 넣어서 해야되나 생각했었는데

현재 큐의 사이즈를 가지고 i < size - 1 이것으로 rightmost 한 노드를 제외하고 next 에 연결시킬 수 있었다.

아 진짜 풀 수 있었는데~~~~~~(못 풀었을테지만) ㅋㅋㅋㅋㅋㅋㅋㅋ 하면서 기쁜 마음으로 솔루션 보면서 소스 수정했다

 

728x90
반응형

'자료구조 알고리즘 > 코딩테스트' 카테고리의 다른 글

Lowest Common Ancestor of a Binary Tree  (0) 2021.06.26
Populating Next Right Pointers in Each Node II  (0) 2021.06.25
Construct Binary Tree from Preorder and Inorder Traversal  (0) 2021.06.23
Construct Binary Tree from Inorder and Postorder Traversal  (0) 2021.06.22
Count Univalue Subtrees  (0) 2021.06.21
  1. 116. Populating Next Right Pointers in Each Node
'자료구조 알고리즘/코딩테스트' 카테고리의 다른 글
  • Lowest Common Ancestor of a Binary Tree
  • Populating Next Right Pointers in Each Node II
  • Construct Binary Tree from Preorder and Inorder Traversal
  • Construct Binary Tree from Inorder and Postorder Traversal
내공얌냠
내공얌냠
내공냠냠
내공얌냠
내공냠냠
내공얌냠
전체
오늘
어제
  • 분류 전체보기 (255) N
    • 개발 (113)
      • mediapipe (16)
      • insightface (5)
      • JongjuAR (3)
    • 자료구조 알고리즘 (79)
      • 코딩테스트 (64)
      • 이론 (15)
    • 공부 (54) N
      • 단행본 (8) N
      • 튜토리얼 (19)
      • 논문 (15)
      • 복기 (5)
    • 참여 (5)

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

인기 글

태그

  • flutter tutorial
  • speaker adaptation tts
  • ios google places api
  • flutter conference
  • postgresql install in mac
  • mediapipe
  • 플러터
  • 컴퓨터 비전 기초
  • 플러터 튜토리얼
  • 구글 미디어파이프
  • 머신러닝이란
  • 딥러닝 기반 음성인식 기초
  • flutter
  • 테디노트의 랭체인을 활용한 rag 비법노트 기본편
  • 테디노트의 랭체인을 활용한 rag 비법노트 기본편 후기
  • git tutorial
  • 테디노트 rag 기본편
  • 컴퓨터 비전 책 추천
  • postgresql 재설치
  • mediapipe translate
  • google mediapipe
  • 컴퓨터 비전
  • python telegrambot
  • 깃 튜토리얼
  • flutter 행사 후기
  • 음성인식 튜토리얼
  • flutter 행사
  • vscode 스프링 설치
  • 음성인식 기초
  • 미디어파이프

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
내공얌냠
Populating Next Right Pointers in Each Node
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.