題目描述
給定一個二叉樹和其中的一個結點，請找出中序遍歷順序的下一個結點并且回傳，注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指標， 思路： 要分幾種情況： （1）結點有右結點，則其下一個結點為其右結點的最左子節點， （2）結點無右結點，且是其父節點的左節點，則其下一個結點為其父節點， （3）結點無右結點，其是其父節點的右結點，則其有如下兩種情況：
第一種情況需要不斷的向上回溯，第二種情況下一個結點就是其父節點，
代碼如下：
/* 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) { TreeLinkNode * rev; if(pNode==NULL) return NULL; if(pNode->right!=NULL) { rev=pNode->right; while(rev->left!=NULL) rev=rev->left; return rev; } else { if(pNode->next==NULL) { return NULL; } if(pNode->next->left==pNode) { return pNode->next; } rev=pNode; while(rev->next!=NULL&&rev==rev->next->right) { rev=rev->next; } return rev->next; } } };
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/24594.html
標籤：其他
上一篇：序列化二叉樹
下一篇：鏈表中環的入口結點