解题思路

• 先向前寻找，直至找到根节点；
• 中序遍历数；
• 在遍历后的结果内查找是否有目标节点，如果有则返回其下一个节点；
• 否则，返回空。

复杂度

• 时间复杂度为O（n）；
• 空间复杂度为O（n）。

代码

Python

class Solution:
    node = []

    def inOrder(self, root):
        if root is None:
            return 
        
        self.inOrder(root.left)
        self.node.append(root)
        self.inOrder(root.right)

    def GetNext(self, pNode):
        root = pNode

        # 从后往前找，直到根节点
        while root.next:
            root = root.next

        # 中序遍历得到结果
        self.inOrder(root)

        # 找到匹配的结果，并返回其下一个节点
        for i in range(len(self.node)-1):
            cur = self.node[i]

            if pNode == cur:
                return self.node[i+1]
        return None

C++

class Solution {
public:
    vector<TreeLinkNode*> res;

    void inOrder(TreeLinkNode* root)
    {
        if(root == NULL)
        {
            return ;
        }

        inOrder(root->left);
        res.push_back(root);
        inOrder(root->right);
    }

    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        TreeLinkNode* root = pNode;
        while(root->next)
        {
            root = root->next;
        }

        inOrder(root);

        for(int i = 0; i < res.size(); i++)
        {
            if(res[i] == pNode)
            {
                return res[i+1];
            }
        }

        return NULL;       
    }
};