LeeCode_Populating Next Right Pointers in Each Node II
3141 단어 LeetCode
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
You may only use constant extra space.
For example, Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
제목이 위에서 보듯이 이 문제는 I에서 추궁한 결과 첫 번째 문제가 너무 빨리 제출되어 이 문제의 대의를 초래했다. 원래는 귀속적인 방법으로 해답을 구하려고 했지만 해답의 확장 방향이 명확하지 않아 잡담을 하지 않고 바로 그림을 그렸다.
코드는 다음과 같습니다.
class Solution {
public:
void connect(TreeLinkNode *root) {
TreeLinkNode *pLeftMost=root;
while (pLeftMost!=NULL){
TreeLinkNode *ptemp=pLeftMost;
while (ptemp!=NULL){
connectToNext(ptemp);
ptemp=ptemp->next;
}
pLeftMost= findLeftMost(pLeftMost);
}
pLeftMost = root;
while (pLeftMost!=NULL){
TreeLinkNode *tep=pLeftMost;
while (tep!=NULL)
{
cout<<tep->val<<" ";
tep=tep->next;
}
cout<<"# ";
pLeftMost= findLeftMost(pLeftMost);
}
}
TreeLinkNode *findLeftMost(TreeLinkNode *preLeftMost){
while (preLeftMost!=NULL){
if(preLeftMost->left!=NULL)
{
return preLeftMost->left;
}
if (preLeftMost->right!=NULL)
{
return preLeftMost->right;
}
preLeftMost=preLeftMost->next;
}
return NULL;
}
void connectToNext(TreeLinkNode *root){
if (root==NULL)
{
return;
}
TreeLinkNode *pSet=root->left;
TreeLinkNode *pSetNext=NULL;
//
if (pSet!=NULL){
// , next
// next
if(root->right!=NULL){
pSet->next=root->right;
pSet=root->right;
}
}
else{
// , next
pSet=root->right;
}
//
if (pSet==NULL)
{
/*connectToNext(root->next);*/
return;
}
//find pSet's next
TreeLinkNode *ptemp=root->next;
while (ptemp!=NULL){
if (ptemp->left!=NULL){
pSetNext=ptemp->left;
break;
}
if (ptemp->right!=NULL){
pSetNext=ptemp->right;
break;
}
ptemp=ptemp->next;
}
pSet->next=pSetNext;
/* connectToNext(root->next);*/
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.