[Leetcode] 117. Populating Next Right Pointers in Each Node II 문제 풀이

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

Populating Next Right Pointers in Each Node II - LeetCode

 

문제 내용

이진 트리에 next 라는 같은 레벨에서 옆을 가리키는 포인트를 추가하는 문제

 

Example 1:

예제1번 그림

Input: root = [1,2,3,4,5,null,7]

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

Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

 

문제 풀이

bfs를 이용해서 문제를 푸려고 했으나 조건에서 추가적인 메모리를 사용하지 않게 풀어라고 해서 dfs로 풀었다.

 

dfs로 방문할때 자식의 next 노드를 하나씩 연결시켜갔다.

right 먼저 방문해서 right의 노드를 다 업데이트 한 다음에

next는 하나씩 탐색하면서 null이 아닌 노드를 찾아서 연결시켰다.

/*
// 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:
    void dfs(Node* node) {
        if (node == nullptr)
            return;
        
        auto child = node->left;
        auto next = node->right;
        
        if (child != nullptr) {
            child->next = next;
        }
        if (next != nullptr) {
            child = next;
        }
        
        if (child == nullptr)
            return;
        
        next = nullptr;
        auto node1 = node->next;
        while(node1 != nullptr) {
            if (node1->left != nullptr) {
                next = node1->left;
                break;
            }
            if (node1->right != nullptr) {
                next = node1->right;
                break;
            }
            node1 = node1->next;
        }
        
        child->next = next;

        dfs(node->right);
        dfs(node->left);
    }
    Node* connect(Node* root) {
        dfs(root);
        return root;
    }
};