leetcode || 116、Populating Next Right Pointers in Each Node

problem:
Given a binary tree
    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to  NULL .
Initially, all next pointers are set to  NULL .
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example, Given the following perfect binary tree,
         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Hide Tags
 
Tree Depth-first Search
제목: 두 갈래 나무의 모든 노드에next 바늘을 추가하고 두 갈래 나무의 모든 노드를 연결합니다
thinking:
(1) B* 트리와 유사하며 각 레이어 노드도 연결됩니다.
(2) 문제를 보자마자 저는 여러 차례 반복해서 BFS를 사용하려고 했습니다. 그러나 제목은 constant extra space를 요구했습니다. 목적은 DFS로 하려고 했습니다. 이 문제의 두 갈래 나무의 특수성(만수)은 보편적인 의미를 가지지 않기 때문입니다.그래서 저는 더 보편적인 BFS 방법을 사용합니다. 공간의 복잡도가 요구에 부합되지 않을 수도 있지만 AC도 있습니다.
(3) BFS는queue 구조로 각 층을 저장하는 노드입니다.
code:
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root==NULL)
            return;
        queue<TreeLinkNode*> queue0;
        queue0.push(root);
        level_visit(queue0);
        return;
    }
protected:
    void level_visit(queue<TreeLinkNode*> queue1)
    {
        if(queue1.empty())
            return;
        queue<TreeLinkNode*> queue2=queue1;
        queue<TreeLinkNode*> queue3;
        TreeLinkNode *tmp=queue1.front();
        queue1.pop();
        tmp->next=NULL;
        while(!queue1.empty())
        {
            TreeLinkNode *tmp2=queue1.front();
            queue1.pop();
            tmp2->next=NULL;
            tmp->next=tmp2;
            tmp=tmp2;
        }
        while(!queue2.empty())
        {
            TreeLinkNode *node=queue2.front();
            queue2.pop();
            if(node->left!=NULL && node->right!=NULL)
            {
                queue3.push(node->left);
                queue3.push(node->right);
            }
        }
        level_visit(queue3);
    }
    
};

좋은 웹페이지 즐겨찾기