二叉树的中序后继（不是 BST）

Question

有人可以帮我弄清楚如何找到给定节点（不是二叉搜索树）的二叉树的中序后继者吗？我知道如何在二叉搜索树中找到它：它将是右子树的最左边的叶子。但是，我不确定如果树不是 BST，它是如何完成的。

我不认为我可以先转到右子节点，然后再转到最左边的叶节点。 （或者在 BST 和普通 BT 中寻找中序后继者之间有区别吗？

谢谢你。

Answer 1

BST 和普通 BT 中寻找中序后继者有区别吗？

不，没有。中序排序通常适用于二叉树。

效果的唯一区别是，BST 上的中序遍历将产生按值“有序”的值序列。但这只是适用于 BST 的一个很好的属性。它不影响 inorder 所代表的含义。

我们可以编写一个递归函数来查找二叉树的中序后继者。时间复杂度为 O(n)，其中 n -> 二叉树中的节点数。这比 BST 的情况要大得多，其中时间复杂度为 O(log(n))，因为我们可以在每次调用中拒绝左子树或右子树。

Answer 2

代码如下，我们维护下一个指针，该指针的值是当前节点的后继节点。我们首先移动到右孩子，然后处理，然后移动到左孩子。 请注意，每当我们找到要搜索的后继节点时，我们都会返回下一个节点，并且不会进一步处理。

class Solution {
private:
    TreeNode* fun(TreeNode* node, TreeNode* p, TreeNode* &next) {
        if (!node) 
            return NULL;
    
        TreeNode* right = fun(node->right, p, next);
        if (right) return right;
        if (node == p) return next;
        next = node;

        TreeNode* left = fun(node->left, p, next);
        if (left) return left;
        return NULL;
    }
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (!root || !p)
            return NULL;
        TreeNode* next = NULL;
        return fun(root, p, next);
    }
};