LeetCode Lowest Common Ancestor of a Binary Search Tree

LeetCode Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.


给定一棵二叉搜索树和两个节点,问这两个节点的最近公共祖先(LCA)。LCA问题很久以前在hihoCoder上做过好多,用到一些比较高级的算法。

这个题的一个特点是二叉树是二叉搜索树,二叉搜索树的特点是左孩子小于等于根节点,根节点小于等于右孩子。不失一般性,令p<=q,所以如果p<=root<=q,则p,q分立root两边,则root就是p,q的LCA。如果p,q都小于root,则递归在root->left找。如果p,q都大于root,则递归在root->right找。

递归的算法很容易就实现了,代码如下:

class Solution {
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if (p->val > q->val)swap(p, q);
		if (p->val <= root->val&&q->val >= root->val)return root;
		if (p->val < root->val&&q->val < root->val)return lowestCommonAncestor(root->left, p, q);
		if (p->val > root->val&&q->val>root->val)return lowestCommonAncestor(root->right, p, q);
	}
};

本代码提交AC,用时32MS。

Leave a Reply

Your email address will not be published. Required fields are marked *