剑指offer（C++）——二叉树的下一个结点

野性酷女 2022-06-17 05:43 160阅读 0赞

## 题目描述 ##

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

struct TreeLinkNode {
    	int val;
    	struct TreeLinkNode *left;
    	struct TreeLinkNode *right;
    	struct TreeLinkNode *next;
    	TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {}
    };
    
    /*思路：分两种情况考虑：
    （1）当前结点有右子树时：只要从当前结点的右子结点开始，沿着左指针一直寻找下去，最终结点就是当前结点的下一个结点
    （2）当前结点没有右子树：a、如果当前结点是其父节点的左子结点，则下一个结点就是其父节点；
                             b、如果当前结点是其父节点的右子结点，就沿着指向父节点的指针一直向上遍历，直到找到一个结点是其父节点的左子结点为止，这个父节点就是下一个结点*/
    class Solution {
    public:
    	TreeLinkNode* GetNext(TreeLinkNode* pNode)
    	{
    		if (pNode == NULL)
    			return NULL;
    		TreeLinkNode* pNext = NULL;
    
    		//如果当前结点有右子树，那么当前结点的下一个结点为其右子树中最左结点
    		if (pNode->right != NULL)
    		{
    			TreeLinkNode* pRight = pNode->right;
    			while (pRight->left != NULL)               //沿右结点的指向左子结点指针一直找下去
    				pRight = pRight->left;
    			pNext = pRight;
    		}
    		else if(pNode->next!=NULL)
    		{
    			TreeLinkNode* pCurrent = pNode;                                 //始终指向当前遍历的结点
    			TreeLinkNode* pParent = pNode->next;                            //始终指向父节点
    			while (pParent != NULL&&pCurrent == pParent->right)             //沿着父指针一直向上遍历
    			{
    				pCurrent = pParent;
    				pParent = pParent->next;
    			}
    			pNext = pParent;                 //父节点就是下一个结点（或者父节点为空，说明没有下一个结点）
    		}
    		return pNext;
    	}
    };