程序员面试金典--二叉树的下一个结点
题目描述
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
题解:
分情况, 如果当前点的右节点为空,则需要返回到其父节点。 (而且它不能是父节点的右孩子,不然继续往上找);
如果当前节点的右节点不空, 则一直找它的左孩子即可。
/* 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->right == NULL ){ TreeLinkNode *pre = pNode, *t = pNode->next; while(t!=NULL && pre == t->right){ pre = t; t = t->next; } return t; } else { TreeLinkNode *t = pNode->right; while(t->left != NULL){ t = t->left; } return t; } } };