LeetCode(Oct28'12):Populating Next Right Pointers in Each Node

2054 단어
Leet Code를 처음 해봤는데 간단한 제목을 골랐어요. 먼저 환경을 익혀보세요.
제목은 다음과 같습니다.
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

사실은 완전한 두 갈래 나무에 같은 층의 노드를 체인 시계로 꿰매는 것이다. 체인 시계의 구조는 나무 노드에서도 이미 제시되었다.다음은 다음과 같습니다.
class Solution {
public:
    void connect(TreeLinkNode *root) {
		for(;root!=NULL;root=root->left)
		{
			createConnect(root->left,root);
		}
    }

    void createConnect(TreeLinkNode *dest,TreeLinkNode *parent)
    {
		if(dest==NULL) return;
         TreeLinkNode *tmpP,*tmpD;
         dest->next=parent->right;
         for(tmpP=parent->next,tmpD=dest->next;tmpP!=NULL;tmpP=tmpP->next,tmpD=tmpD->next->next)
		 {
                tmpD->next=tmpP->left;
                tmpD->next->next=tmpP->right;
		 }
    }
};

프로그램은 매우 간단해서 말할 만한 알고리즘이 없다.위에서 아래로 각 층을 순환하고 반복할 때 아버지의 노드를 가지고 있다. 아버지의 노드는 이미 체인식 구조를 형성했기 때문에 이 층 노드의next에 하나씩 값을 부여하면 된다.질문: 1. NULL 노드를 입력하고 고려하지 않으면 Runtime Error를 보고합니다.2. 하나의 노드만 있고 노드의 각 포인터의 NULL 상황을 고려한다.3. 첫 번째 부모 노드를 연결한 두 아이가 현재 처리된 노드를 뒤로 옮기지 않아 층수 >=4의 경우 중간 노드는 내부만 연결되고 전체 체인에 연결되지 않는다(건너뛰었기 때문이다).마지막으로 부모 노드만 윗층의 첫 번째와 마지막 아이의 노드로 연결된다.PS. csdn의 편집기도 너무 어렵죠...
Tempdb--Allocation Bottleneck
form 폼 서열화 결과 json 형식의

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage