题解 | #二叉树的下一个结点#

迭代法

使用栈来中序遍历，当节点值相同的时候，标志flag为true，再下一次拿到节点就是下一个节点并返回

注意由于传入的不一定是根节点，所以需要先拿到根节点

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
#include <stack>
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        //中序遍历
        stack<TreeLinkNode*> st;
        
        TreeLinkNode*cur=pNode;
        while (cur->next!=nullptr) {
            cur=cur->next;
        }

        //这里{5,4,#,3,#,2},4，出错的原因是传入的不是根节点，导致栈没有保存5
        bool flag=false;
        while(!st.empty()||cur!=nullptr){
            while(cur!=nullptr)
            {   
                st.push(cur);
                cur=cur->left;
            }

            cur=st.top();
            st.pop();
            if(flag){
                return cur;
            }
            if(cur->val==pNode->val)
            {
                flag=true;
            }
        
            cur=cur->right;
        }
        return nullptr;
    }
};