思路

题目分析

1. 题目给出我们一棵树的其中的某一个结点指针
2. 我们需要返回这棵树按照中序遍历的该节点的下一个顺序结点指针
3. 树的每个节点都有三个指针，指向左子节点、右子节点、父节点

• 方法一：中序遍历
  • 首先先根据当前给出的结点找到根节点
  • 然后根节点调用中序遍历
  • 将中序遍历结果存储下来
  • 最终拿当前结点匹配是否有符合要求的下一个结点
• 方法二：直接寻找
  • 直接寻找分为三种情况
    • 如果给出的结点有右子节点，则最终要返回的下一个结点即右子树的最左下的结点
    • 如果给出的结点无右子节点，且当前结点是其父节点的左子节点，则返回其父节点
    • 如果给出的结点无右子节点，且当前结点是其父节点的右子节点，则先要沿着左上方父节点爬树，一直爬到当前结点是其父节点的左子节点为止，返回的就是这个左子节点；或者没有满足上述情况的则返回为NULL

方法一：中序遍历

/*
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:
    vector<TreeLinkNode*> nodes;
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        TreeLinkNode* root = pNode;
        while(root->next) root = root->next;    // 获取根节点
        
        InOrder(root);                          // 中序遍历用nodes储存所有节点指针
        int n = nodes.size();
        
        for(int i = 0; i < n - 1; i++) {
            TreeLinkNode* cur = nodes[i];       
            if(pNode == cur) {                  // 将结点进行匹配
                return nodes[i+1];              // 如果有匹配到给出的结点，则下一个结点即返回结果
            }
        }
        return NULL;                            // 否则如果没有下一个结点则返回NULL
    }
    void InOrder(TreeLinkNode* root) {          // 中序遍历
        if(root == NULL) return;
        InOrder(root->left);
        nodes.push_back(root);
        InOrder(root->right);
    }
};

复杂度分析

• 时间复杂度：$O\left(N\right)O(N)$O(N)，因为遍历了树中的所有节点
• 空间复杂度：$O\left(N\right)O(N)$O(N)，因为引入了存储所有节点的空间

方法二：直接寻找

/*
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->right) {    // 如果有右子树
            TreeLinkNode* rchild = pNode->right;
            while(rchild->left) rchild = rchild->left;    // 一直找到右子树的最左下的结点为返回值
            return rchild;
        }
        
        if(pNode->next && pNode->next->left == pNode) {    // 如果无右子树且当前结点是其父节点的左子结点
            return pNode->next;   // 返回当前结点的父节点
        }
        
        if(pNode->next) {         // 如果无右子树且当前结点是其父节点的右子节点
            TreeLinkNode* ppar = pNode->next;
            while(ppar->next && ppar->next->right == ppar) ppar = ppar->next;    // 沿着左上一直爬树，爬到当前结点是其父节点的左自己结点为止
            return ppar->next;    // 返回当前结点的父节点
        }
        return NULL;
    }
};

复杂度分析

• 时间复杂度：$O\left(logN\right)O(logN)$O(logN)，最大代价是从树的叶子结点爬到根节点的时间
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外空间的借用