剑指Offer刷题（二叉树的下一个结点）

一.题目描述二.代码（C++）三.提交记录四.备注

一.题目描述

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

二.代码（C++）

/* 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) return nullptr; if(pNode->right) { pNode = pNode->right; while(pNode->left) { pNode = pNode->left; } return pNode; } while(pNode->next) { if(pNode->next->left==pNode) return pNode->next; pNode = pNode->next; } return NULL; } };

三.提交记录

四.备注

画图，找规律即可。