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

/*
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* zxbianli(TreeLinkNode* pNode,TreeLinkNode* node)
{
    static TreeLinkNode* tree = nullptr;
    static int k=0;
    if (pNode)
    {
        if (pNode->left)
            zxbianli(pNode->left,node);
                        if(k)
            {
                tree=pNode;
                k=0;
            }
            cout<<'!'<<pNode->val;
        if (pNode==node)
            k=1;

        if (pNode->right)
            zxbianli(pNode->right,node);


    }
    return tree;



}






    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
       

       static TreeLinkNode* head = nullptr;
       static TreeLinkNode *node=pNode;

        while(!head)
        {
            if(pNode->next)
            pNode=pNode->next;
            else head=pNode;
        }
        
        cout<<head->val<<'-'<<node->val;
        head=zxbianli(head,node);



        return head;

    }
};

一开始想复杂了,其实这道题只需要先找到根节点,然后在中序遍历就行了.

我一开始想的是怎么不找到根节点然后找下一个,但实际上找根节点很简单,复杂度低,是一个好方法.