中序遍历，二叉树的下一个结点（全面梳理分支情况）
二叉树的下一个结点
http://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e
- 解法1（明明很认真梳理，但是按这个顺序来，耗费时间却更多，不知道为啥）
根据牛客官方题解给的图，梳理出来了所有情况（花了好多时间，就为了全面，不遗漏什么。。。。我的大把时间那），并根据这些情况编码
蓝色的是很简单的，红色的最难，因为需要回溯的步数多。但是这些情况中，很多都需要回溯，所以这道题提供的结构体中存储了父亲结点的信息。
/*
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)
{
//为空，或者只有一个根结点
if(!pNode || (!pNode->next && !pNode->left && !pNode->right))//空树或只有一个节点
return nullptr;
TreeLinkNode * t, *res;
//根节点,但树中有多于一个节点
if (!pNode->next)
{
t = pNode->right;
if (!t)
return t;
res = t->left;
while (res)
{
t = res;
res = res->left;
}
return t;
}
//当前节点有右孩子，则下一节点是右孩子的第一个没有左孩子的左孩子，如果当前节点的右孩子没有左孩子，那下一节点就是右孩子
if (pNode->right)
{
t = pNode->right;
res = t->left;
if (!res)
return t;
while (res)
{
t = res;
res = res->next;
}
return t;
}
//没有右孩子且是父亲的左孩子，下一节点是父亲
if (!pNode->right && pNode->next->left == pNode)
return pNode->next;
//没有右孩子，是父亲的右孩子
if (!pNode->right && pNode==pNode->next->right)
{
//如果爷爷存在，即父亲不是根节点,且父亲是爷爷的左孩子，则下一节点是爷爷
if (pNode->next->next && pNode->next==pNode->next->next->left)
return pNode->next->next;
//当前节点是根节点的最右孩子，则下一结点是空
if (!pNode->left && !pNode->right)//传入的是叶子，不是根
{
res = pNode;
while (res->next)
res = res->next;
//退出前面的while后，res是根节点
//s = res->right;
while (res->right)
res = res->right;
//退出前面while，res是根的最右孩子;若根没有右孩子则res是根自己
if (res==pNode)
return nullptr;
}
//如果爷爷存在，即父亲不是根节点,且父亲是爷爷的右孩子,则下一结点是一路回溯中遇到的第一个是自己父亲的左孩子的祖先结点
if (pNode->next->next && pNode->next==pNode->next->next->right)
{
t = pNode->next->next;
while (t)
{
res = t;
t = t->next;
if (!t || t->left == res)//!t成立则回溯到了根结点
return t;
}
}
}
}
}; - 解法2（感觉漏掉了最后一种最难的情况，但是也通过了。。。。）
比如下面这棵树的结点4，中序遍历（顺序是123478）的下一个结点是7，就属于红色情况。但是不知道为啥我这版代码没考虑这种情况也过了。。。。
/*
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)
{
if(!pNode || (!pNode->next && !pNode->left && !pNode->right))//空树或只有一个节点
return nullptr;
TreeLinkNode * t, *res;
if (!pNode->next)//根节点,但树中有多于一个节点
{
t = pNode->right;
if (!t)
return t;
res = t->left;
while (res)
{
t = res;
res = res->left;
}
return t;
}
//情况1，没有右孩子且是父亲的左孩子，下一节点是父亲
if (!pNode->right && pNode->next->left == pNode)
return pNode->next;
//情况2，没有右孩子，是父亲的右孩子，且父亲是爷爷的左孩子，则下一节点是爷爷
if (!pNode->right && pNode==pNode->next->right)
{
//如果爷爷存在，即父亲不是根节点,且父亲是爷爷的左孩子
if (pNode->next->next && pNode->next==pNode->next->next->left)
return pNode->next->next;
}
//情况3，当前节点是根节点的最右孩子，则下一结点是空
if (!pNode->left && !pNode->right)//传入的是叶子，不是根
{
res = pNode;
while (res->next)
res = res->next;
//退出前面的while后，res是根节点
//s = res->right;
while (res->right)
res = res->right;
//退出前面while，res是根的最右孩子;若根没有右孩子则res是根自己
if (res==pNode)
return nullptr;
}
//情况4，当前节点有右孩子，则下一节点是右孩子的第一个没有左孩子的左孩子，如果当前节点的右孩子没有左孩子，那下一节点就是右孩子
if (pNode->right)
{
t = pNode->right;
res = t->left;
if (!res)
return t;
while (res)
{
t = res;
res = res->next;
}
return t;
}
}
}; - 优化（把根结点的最右孩子的情况单独拿出来判断，时间正常了）
因为向第一种方案那样放在最里面有重复判断，如果把重复判断优化掉，也会减少时间的。
/*
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)
{
//为空，或者只有一个根结点
if(!pNode || (!pNode->next && !pNode->left && !pNode->right))//空树或只有一个节点
return nullptr;
TreeLinkNode * t, *res;
//根节点,但树中有多于一个节点
if (!pNode->next)
{
t = pNode->right;
if (!t)
return t;
res = t->left;
while (res)
{
t = res;
res = res->left;
}
return t;
}
//当前节点是根节点的最右孩子，则下一结点是空
if (!pNode->left && !pNode->right)//传入的是叶子，不是根
{
res = pNode;
while (res->next)
res = res->next;
//退出前面的while后，res是根节点
//s = res->right;
while (res->right)
res = res->right;
//退出前面while，res是根的最右孩子;若根没有右孩子则res是根自己
if (res==pNode)
return nullptr;
}
//当前节点有右孩子，则下一节点是右孩子的第一个没有左孩子的左孩子，如果当前节点的右孩子没有左孩子，那下一节点就是右孩子
if (pNode->right)
{
t = pNode->right;
res = t->left;
if (!res)
return t;
while (res)
{
t = res;
res = res->next;
}
return t;
}
//没有右孩子且是父亲的左孩子，下一节点是父亲
if (!pNode->right && pNode->next->left == pNode)
return pNode->next;
//没有右孩子，是父亲的右孩子
if (!pNode->right && pNode==pNode->next->right)
{
//如果爷爷存在，即父亲不是根节点,且父亲是爷爷的左孩子，则下一节点是爷爷
if (pNode->next->next && pNode->next==pNode->next->next->left)
return pNode->next->next;
//如果爷爷存在，即父亲不是根节点,且父亲是爷爷的右孩子,则下一结点是一路回溯中遇到的第一个是自己父亲的左孩子的祖先结点
if (pNode->next->next && pNode->next==pNode->next->next->right)
{
t = pNode->next->next;
while (t)
{
res = t;
t = t->next;
if (!t || t->left == res)//!t成立则回溯到了根结点
return t;
}
}
}
}
}; 
微软公司氛围 71人发布
查看15道真题和解析