剑指Offer——JZ57.二叉树的下一个结点【中序遍历】

剑指Offer——JZ57.二叉树的下一个结点【中序遍历】

​​题目传送门​​

题解

找到跟结点，中序遍历即可

AC-Code

/*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 NULL; TreeLinkNode * p = pNode; while(p->next) { // 寻找根节点 p = p->next; } stack st; bool flag = false; // 标记 while(!st.empty() || p) { while(p) { st.push(p); p = p->left; } if(!st.empty()) { p = st-(); st.pop(); if(flag) return p; if(pNode == p) flag = true; p = p->right; } } return NULL; } };

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。