编写算法，在二叉排序树上找出任意两个不同结点的最近公共祖先

1. 从根节点开始遍历二叉排序树，如果根节点为空或者等于其中一个结点，则返回根节点。
2. 如果根节点的值大于两个结点的值，则在左子树中继续查找。
3. 如果根节点的值小于两个结点的值，则在右子树中继续查找。
4. 如果根节点的值在两个结点的值之间，则说明根节点就是最近公共祖先，直接返回根节点。

相关问题

用C++编写算法,在二叉排序树中找出任意两个不同节点的最近公共祖先

以下是用C++编写的算法，它使用了递归的方法，在二叉排序树中找出任意两个不同节点的最近公共祖先：

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return NULL;  // 如果根节点为空，返回NULL
    if (root->val > p->val && root->val > q->val) {
        return lowestCommonAncestor(root->left, p, q);  // 如果根节点大于p和q的值，那么p和q在根节点的左子树中，递归左子树
    } else if (root->val < p->val && root->val < q->val) {
        return lowestCommonAncestor(root->right, p, q);  // 如果根节点小于p和q的值，那么p和q在根节点的右子树中，递归右子树
    } else {
        return root;  // 如果根节点的值介于p和q的值之间，那么根节点就是它们的最近公共祖先
    }
}

int main() {
    TreeNode* root = new TreeNode{6, NULL, NULL};
    root->left = new TreeNode{2, NULL, NULL};
    root->right = new TreeNode{8, NULL, NULL};
    root->left->left = new TreeNode{0, NULL, NULL};
    root->left->right = new TreeNode{4, NULL, NULL};
    root->left->right->left = new TreeNode{3, NULL, NULL};
    root->left->right->right = new TreeNode{5, NULL, NULL};
    root->right->left = new TreeNode{7, NULL, NULL};
    root->right->right = new TreeNode{9, NULL, NULL};

    TreeNode* p = root->left->right->left;
    TreeNode* q = root->left->right->right;
    TreeNode* lca = lowestCommonAncestor(root, p, q);
    cout << "Lowest Common Ancestor of " << p->val << " and " << q->val << " is " << lca->val << endl;

    return 0;
}

该程序的输出结果是：

Lowest Common Ancestor of 3 and 5 is 4

其中，root是二叉排序树的根节点，p和q是任意两个不同的节点，lca是它们的最近公共祖先。

java二叉排序树上找结点x的算法

在Java中，可以通过以下代码实现在二叉排序树上找结点x的算法：

public Node search(Node root, int x) {
    if (root == null || root.val == x) {
        return root;
    }
    if (root.val > x) {
        return search(root.left, x);
    }
    return search(root.right, x);
}

其中，Node表示二叉排序树的节点，val表示节点的值，left表示左子树，right表示右子树。该算法使用递归实现，在每个节点上比较节点的值与x的大小关系，继续查找左子树或右子树，直到找到节点值等于x的节点或遍历到叶子节点仍未找到。如果根节点为null或根节点的值等于x，则直接返回根节点。