难在认清楚 所有出口
梳理所有的出口,并且代码简洁的输出
- 最难之一的在找出 父亲的左儿子==自己的场景。
code
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
*/
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode) {
//中序下一个
//至少3个出口, 首先要构建一个可用的测试用例
if(pNode == NULL){
return NULL;
}
//参数判定
//002 右子树 左到底
if(pNode->right){
pNode = pNode->right;
while(pNode->left !=NULL){
pNode = pNode->left;
}
return pNode;
}
//003 向上找, 爸爸= 爷爷的左儿子 为止
TreeLinkNode *upNode =NULL;
while(pNode->next !=NULL){
upNode = pNode->next;
//found it ,then return;
if(upNode->left == pNode){
return upNode;
}
//not found, update
pNode = pNode->next;
}
//004 找不到,最
return NULL;
}
};
more 混乱的逻辑 体现
不知道如何终结,节点也写比较多;抓住一个 上溯的节点就可以了
//混乱的逻辑
TreeLinkNode * baba = NULL ;
TreeLinkNode * yeye = NULL ;
if(pNode->next){
baba = pNode->next;
if(baba && baba->next){
yeye = baba->next;
while(yeye->left !=baba ){
baba = baba->next;
yeye = baba->next->next; //注意判空
}
}
}