題目描述
- 給定一棵二叉樹和其中的一個(gè)節(jié)點(diǎn)，如何找出中序遍歷序列的下一個(gè)節(jié)點(diǎn)累提？
- 樹中的節(jié)點(diǎn)除了有兩個(gè)分別指向左、右子節(jié)點(diǎn)的指針，還有一個(gè)指向父節(jié)點(diǎn)的指針
struct TreeLinkNode {
int val;
struct TreeLinkNode *left; // 左孩子
struct TreeLinkNode *right; // 右孩子
struct TreeLinkNode *next; // 父節(jié)點(diǎn)
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {}
};
題目解讀
代碼
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode){
TreeLinkNode *p, *c, *next;
if(pNode == NULL){
return NULL;
}
// 如果該節(jié)點(diǎn)有右子樹
if(pNode->right != NULL){
p = pNode->right;
while(p->left != NULL){
p = p->left;
}
next = p;
} // 執(zhí)行 else if 證明該節(jié)點(diǎn)沒有右子樹
else if(pNode->next != NULL){
p = pNode->next;
c = pNode;
while(p!=NULL && c == p->right){
c = p;
p = p->next;
}
next = p;
}
return next;
}
};
總結(jié)展望
- 看書思路不難幌羞，容易理解，然后自己手寫了竟稳；但是属桦，我認(rèn)為我的代碼沒問題，沒想到提交到潘郑客網(wǎng)報(bào)錯(cuò)為
段錯(cuò)誤:您的程序發(fā)生段錯(cuò)誤聂宾，可能是數(shù)組越界，堆棧溢出（比如诊笤，遞歸調(diào)用層數(shù)太多）等情況引起系谐，實(shí)在是不知道為啥，留待以后第二遍再來解決吧...
(出錯(cuò)代碼在下面已更正 2019/3/3)
- 上面跑正確這個(gè)代碼是參考別人正確代碼寫的讨跟，寫的確實(shí)不錯(cuò)纪他，比我的簡潔！
附錄
- 自己手動(dòng)寫的出錯(cuò)代碼晾匠，有待修改
段錯(cuò)誤:您的程序發(fā)生段錯(cuò)誤茶袒，可能是數(shù)組越界，堆棧溢出（比如凉馆，遞歸調(diào)用層數(shù)太多）等情況引起
// 因?yàn)橹羔槥榭招皆ⅲ鲥e(cuò)代碼
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode){
TreeLinkNode *p;
if(pNode == NULL){
return NULL;
}
//１，節(jié)點(diǎn)有右子樹
if(pNode->right != NULL){
p = pNode->right;
//現(xiàn)在兩種情況
// 1.1 右子樹沒有左節(jié)點(diǎn)澜共，則右子樹根節(jié)點(diǎn)即為中序遍歷下一個(gè)節(jié)點(diǎn)
if(p->left == NULL){
return p;
}
else{ // 1.2 右子樹有左節(jié)點(diǎn)向叉，則沿著右子節(jié)點(diǎn)出發(fā)一直沿著指向左子節(jié)點(diǎn)的指針行進(jìn)
while(p->left != NULL){
p = p->left;
}
return p;
}
}
else // ２ 節(jié)點(diǎn)沒有右子樹
{ // 2.1 節(jié)點(diǎn)是它父節(jié)點(diǎn)的的左子節(jié)點(diǎn)，那么它的下一個(gè)節(jié)點(diǎn)就是它的父節(jié)點(diǎn)
p = pNode->next;
if(pNode == p->left){ // 如果p為空呢咳胃，這就是出錯(cuò)點(diǎn)植康，指針為空，下面為修改之后代碼
return pNode->next;
}
else // 2.2 如果一個(gè)節(jié)點(diǎn)既沒有右子樹展懈，并且它還是它父節(jié)點(diǎn)的右子節(jié)點(diǎn)销睁，
{ //那么沿著指向父節(jié)點(diǎn)的指針一直向上遍歷供璧，直到找到一個(gè)是它父節(jié)點(diǎn)的左子節(jié)點(diǎn)的節(jié)點(diǎn)
while(pNode->next != NULL){
p = pNode->next;
if(p->left == pNode){
return p;
}
pNode = pNode->next;
}
return NULL;
}
}
}
};
// 更正之后的代碼
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode){
TreeLinkNode *p;
if(pNode == NULL){
return NULL;
}
//１，節(jié)點(diǎn)有右子樹
if(pNode->right != NULL){
p = pNode->right;
//現(xiàn)在兩種情況
// 1.1 右子樹沒有左節(jié)點(diǎn)冻记，則右子樹根節(jié)點(diǎn)即為中序遍歷下一個(gè)節(jié)點(diǎn)
if(p->left == NULL){
return p;
} // 1.2 右子樹有左節(jié)點(diǎn)睡毒，則沿著右子節(jié)點(diǎn)出發(fā)一直沿著指向左子節(jié)點(diǎn)的指針行進(jìn)
else {
while(p->left != NULL){
p = p->left;
}
return p;
}
}
else { // ２ 節(jié)點(diǎn)沒有右子樹
p = pNode->next;
if(p != NULL){
// 2.1 節(jié)點(diǎn)是它父節(jié)點(diǎn)的的左子節(jié)點(diǎn)，那么它的下一個(gè)節(jié)點(diǎn)就是它的父節(jié)點(diǎn)
if(pNode == p->left){
return pNode->next;
}
else // 2.2 如果一個(gè)節(jié)點(diǎn)既沒有右子樹冗栗，并且它還是它父節(jié)點(diǎn)的右子節(jié)點(diǎn)演顾，
{ //那么沿著指向父節(jié)點(diǎn)的指針一直向上遍歷，直到找到一個(gè)是它父節(jié)點(diǎn)的左子節(jié)點(diǎn)的節(jié)點(diǎn)
while(pNode->next != NULL){
p = pNode->next;
if(p->left == pNode){
return p;
}
pNode = pNode->next;
}
return NULL;
}
}
else{
return p;
}
}
}
};
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
