두 갈래 트리에 next 포인터 추가

제목은leetcode에서 유래했다.
제목: 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,

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

사고방식: 모든 결점의 넥스트 바늘은 오른쪽에 인접한 결점을 가리키는데 이 순서는 나무의 층차와 일치한다.따라서 우리는 층층이 훑어보는 과정에서 지침을 수정할 수 있다.
STL에서queue의 사용법: 두 갈래 나무의 층차를 훑어보는 것은 일반적으로 대기열을 빌려 이루어져야 한다. 먼저 STL에서queue의 사용법을 보자.
queue q; queue의 기본 조작은 입대: q.push(x);x를 대기열의 끝에 연결합니다.출대:q.pop();팝업 대기열의 헤더 요소는 팝업된 요소의 값을 되돌려 주지 않습니다.방문팀의 첫 번째 요소: q.front (), 즉 가장 먼저 대기열에 눌린 요소입니다.액세스 대열 끝 요소: q.back (), 즉 마지막으로 대기열에 눌린 요소입니다.대기열 비우기 판단: q.empty (), 대기열이 비었을 때true로 돌아갑니다.현재 대기열의 요소 개수에 접근합니다: q.size ().

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root == NULL)
            return;
        queue<TreeLinkNode *> que;
        TreeLinkNode *p;
        que.push(root);
        
        unsigned int i=2;// 2 n 
        while(!que.empty())
        {
            p = que.front();
            que.pop();
            
            if(p->left != NULL)
                que.push(p->left);
            if(p->right != NULL)
                que.push(p->right);

            if(i&(i-1)) // next
                p->next = que.front();
                
            i++;
        }
        
    }
};

주의: 각 층의 가장 오른쪽 결점은 특수합니다. 넥스트 바늘은 NULL이지만, 층계를 할 때 대기열에서 다음 층으로 갔는지 구분할 수 없습니다.그래서 나는 두 갈래 나무가 가득한 수학적 성질을 이용하여 가장 오른쪽 결점인지 아닌지를 판단한다.여기에 비트 연산 기교를 사용하여 하나의 수가 2의 n차멱인지 아닌지를 판단한다.i&(i-1)는 i의 2진법의 맨 오른쪽 1을 0으로 바꾸고 2의 n차멱에 대해 기호가 없는 수는 최고위만 1이기 때문에 i&(i-1)는 0을 얻는다.
메서드 2: 레이어와 레이어 간의 분할을 위해 대기열에 NULL을 추가합니다.이런 방법은 어떤 두 갈래 나무에도 똑같이 적용된다.

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
	public:
		void connect(TreeLinkNode *root) {
			if(root == NULL)  
				return;  

			queue<TreeLinkNode *> q;  
			q.push(root);  
			q.push(NULL);
			TreeLinkNode *k;
			while(!q.empty())  
			{  
				k = q.front();  
				q.pop();
				if(k == NULL)  
				{  
					if(!q.empty()) //  ， NULL  
						q.push(NULL);
				}
				else
				{
				    k->next = q.front();
				    if(k->left != NULL)  
					    q.push(k->left);  
				    if(k->right != NULL)  
					    q.push(k->right);  
				}
			}  

		}
};

방법3: 위의 두 가지 방법 모두 공간의 복잡도를 O(1)로 하지 못했다.그러니까 대열 구조를 쓰지 마세요.뿌리 노드부터 반복할 때 아이를 가로로 연결한다.이 방법의 시간 복잡도는 O(N), 공간 복잡도 O(1)이다.

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        
        if(root == NULL)
            return;
        TreeLinkNode head(0);
        TreeLinkNode *cur, *pre;
        cur = root;
        pre = &head;//head ， root 
        while(cur != NULL)
        {
            if(cur->left != NULL)
            {
                pre->next = cur->left;
                pre = pre->next;
            }
            if(cur->right != NULL)
            {
                pre->next = cur->right;
                pre = pre->next;
            }
            cur = cur->next;
        }
        connect(head.next); // 
    }
};

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

두 갈래 트리에 next 포인터 추가

좋은 웹페이지 즐겨찾기