如題：

給定一個二叉樹和其中的一個結點，請找出中序遍歷順序的下一個結點并且返回。注意，樹中的結點不僅包含左右子結點，同時包含指向父結點 的指針。

這道題目考察對二叉樹中序遍歷的理解，做題的時候，如果沒有思路，簡單畫畫圖，可以幫助理解。

上圖沒有畫出指向父節點的指針，不過，不妨礙分析問題。已知節點，求中序遍歷后一個節點。

如果節點存在右子樹，顯然，后一個節點位于右子樹上最左邊位置，遞歸查找即可。

如果沒有右子樹，且為根節點，顯然，這時候沒有下一個節點。

如果存在父節點，分為兩種情況，如果是父節點的左孩子，下一個節點就是父節點。

如果是父節點的右孩子，這時候，繼續順著父節點指針網上搜索，直到找到一個位于左孩子的父節點，如上圖中的19，是20的左孩子，8的后一個節點即是20。反之，若是，找不到，則沒有。如上圖右下角的7，父節點都位于右孩子。

經過上述分析可知，總共4種情況，依次處理即可。這道題如果沒有思路，一定要畫圖。

下面是本題的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) {} }; */ //這道題畫圖結合圖形可以分析僅存在三種情況 //1. 節點存在右子樹，此時，找到右子樹最左節點即可。 //2. 沒有父節點可直接返回。 //3. 節點不存在右子樹且其存在父節點，且為父節點的左孩子，此時，返回父節點. //4. 節點為父節點右子樹，此時，遞歸向上查找，找到為左孩子的父節點，返回即可。 class Solution { public:TreeLinkNode* GetNext(TreeLinkNode* pNode){//特殊情況處理if (pNode == nullptr)return nullptr;//1. 存在右子樹，找到最左節點if (pNode->right){pNode = pNode->right;while(pNode->left)pNode = pNode->left;return pNode;}//2. 不存在右子樹，且為根節點if (pNode->next == nullptr)return nullptr;//3. 存在父節點，且為父節點的左孩子if (pNode->next->left == pNode)return pNode->next;//4. 存在父節點，且為父節點的右孩子pNode = pNode->next;while (pNode && pNode->next){if (pNode == pNode->next->left)return pNode->next;elsepNode = pNode->next;}return nullptr;} };

=============================================================================================

Linux應用程序、內核、驅動、后臺開發交流討論群(745510310)，感興趣的同學可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。

總結

以上是生活随笔為你收集整理的《剑指offer》c++版本 8.二叉树的下一个结点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。