题解 | #二叉树的下一个结点#
二叉树的下一个结点
http://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e
/*
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 midVis(TreeLinkNode* pNode)
{
if(!pNode->left)
{
return pNode;
}
return midVis(pNode->left); } TreeLinkNode* findParent(TreeLinkNode* pNode) { TreeLinkNode* parent=pNode->next; if(!parent) { return NULL; } if(parent->left == pNode) { return parent; } else if(parent->right == pNode) { return findParent(parent); } return NULL; } TreeLinkNode* GetNext(TreeLinkNode* pNode) { if(!pNode ) //为空,直接返回null { return NULL; } if(!pNode->right)//没有右子树,需要向上寻找 第一个身为左孩子的结点 的双亲结点 { return findParent(pNode); } return midVis(pNode->right);//有右子树,向它的右子树寻找最左结点。 }
};