• 题目难度：中等

  • 题目描述：

    给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示
    图片说明

  • 数据范围：节点数满足 1 ≤ n ≤ 50 ，节点上的值满足 1 ≤ val ≤ 100

  • 要求：空间复杂度 O(1) ，时间复杂度 O(n)

  • 示例1

    输入：
    {8,6,10,5,7,9,11},8
    返回值：9

  • 思路一：模拟中序遍历，记录中序遍历序列

    时间复杂度：O(n)；空间复杂度：O(n)
class Solution {
public:
    vector<TreeLinkNode*> nodes;
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        // 1. Find root node
        TreeLinkNode* root = pNodel;
        while (root->next) root = root->next;

        // 2. InOrder, save InOrder Sequence
        InOrder(root);
        int n = nodes.size();

        // 3. Find pNode node
        for (int i = 0; i < n - 1; ++i) {
            if (pNode == nodes[i]) return nodes[i+1];
        } 
    }

    void InOrder(TreeLinkNode* root) {
        if (root == nullptr) return;
        InOrder(root->left);
        nodes.push_back(root);
        InOrder(root->right); 
    }
}

  • 思路二：直接按情况搜索

    时间复杂度：O(n)；空间复杂度：O(1)
    图片说明 
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        // 有右子树 --> 最左端节点
        if (pNode->right) {
            TreeLinkNode* node1 = pNode->right;
            while (node1->left) node1 = node1->left;
            reutrn node1;
        }
        // 无右子树
        // 1、左节点
        if (pNode->next && pNode->next->left == pNode) return pNode->next;
        // 2、右节点
        if (pNode->next) {
            TreeLinkNode* node2 = pNode->next;
            while (node2->next && node2->next->right == node2) node2 = node2->next;
            return node2->next;
        }
        return nullptr;
    }
}

😘😘😘😘😘😘😘😘😘😘😘