二叉树 寻找中序序列的下一个节点
给定一个二叉树节点,返回中序序列中下一个节点
二叉树结构(包含指向父节点的指针)
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
思路:
中序遍历顺序:左子树=》根节点=》右子树
对于一个给定节点Node 若其右子树不为空,那么中序下一个节点一定在右子树中,是右子树沿着左方向下降的叶子节点
若右子树为空,那么下一个节点一定在其父辈节点中,是父辈节点中第一个左子树包含它的
代码实现:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
//若节点为NULL
if(pNode==NULL)
return NULL;
//若该节点存在右子树,那么下一个节点一定在右子树中
//且是中序序列的第一个,也就是沿着左子树向下直到叶子节点
if(pNode->right!=NULL)
{
TreeLinkNode* node=pNode->right;
while(node->left)
node=node->left;
return node;
}
//否则该节点不存在右子树部分,那么其中序下一个节点一定在其父辈节点中
while(pNode->next!=NULL)
{
TreeLinkNode* pRoot=pNode->next;//其父亲节点
if(pRoot->left==pNode) //找到第一个这样的父辈节点,pNode是该父辈节点的左子树部分
return pRoot;
pNode=pNode->next;
}
//都找不到的话,那么pNode就是根节点
return NULL;
}
其中 node->next访问一个节点的父节点