题目简述
给定二叉树的某个节点pNode,求出该节点在中序遍历中的下一个节点。
算法一:
时间复杂度:O(N)
思路:
1. 利用pNode->next可以找到二叉树的根节点,然后对二叉树经行中序遍历,将遍历的结果存入vector数组中。
2. 遍历数组,如果数组元素与该点匹配,那么数组的下一个节点便是目标节点。
代码:
class Solution { public: vector<TreeLinkNode*> ans; void fun(TreeLinkNode* pHead){ if(pHead->left) fun(pHead->left); ans.push_back(pHead); if(pHead->right) fun(pHead->right); } TreeLinkNode* GetNext(TreeLinkNode* pNode) { if(!pNode) return NULL; TreeLinkNode* pHead=pNode; while(pHead->next) pHead=pHead->next; fun(pHead); for(int i=0;i<ans.size()-1;i++){ if(ans[i]==pNode) return ans[i+1]; } return NULL; } };
算法二:
时间复杂度:O(N)
思路:
分为两种情况:
1.有右子树:
若右子树有左儿子,则找他的左儿子,若他的儿子有左儿子,则继续找,直到没有左儿子为止。
2.没有右子树:
1.若它有祖先节点则找祖先节点,若满足该点在祖先节点左子树上,那么结束寻找直接返回该祖先节点。
2.若找到最后也找不到满足条件的祖先,说明没有下一个节点,那么返回NULL;
图解:
代码:
class Solution { public: TreeLinkNode* GetNext(TreeLinkNode* pNode) { if(!pNode) return NULL; if(pNode->right){ TreeLinkNode* t=pNode->right; while(t->left){ t=t->left; } return t; } while(pNode->next){ if(pNode->next->left==pNode) return pNode->next; pNode=pNode->next; } return NULL; } };