一起刷leetcode(235):Lowest Common Ancestor of a Binary Search Tree


问题来源:leetcode 235题
问题描述:Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

Java代码实现,已AC:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||p==null||q==null)
            return null;
        if(Math.max(p.val,q.val)<root.val)
            return lowestCommonAncestor(root.left,p,q);
        if(Math.min(p.val,q.val)>root.val)
            return lowestCommonAncestor(root.right,p,q);
        else
            return root;
    }
}
已邀请:

PolorGhost

赞同来自:


这道题最暴力的解法,就是普通二叉树寻找LCA,就不说了,想想BST的特性,就能想到最大的小于当前跟的值,那么要找的值就在左子树,反之就在右子树,要是最小的比根节点小,最大的比根节点大,那么久左右字数都要找。于是
解法一:

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

写完啦,好长,估计是有冗余,找找,就是如果小的数在左子树,大的数在右子树,那么当前root就是LCA。所以:
去冗余解法二:
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL){
            return NULL;
        }
        if (p->val > q->val){
            swap(p, q);
        }
        TreeNode *ans = dfs(root, p, q);
        return ans;
    }
    
    TreeNode *dfs(TreeNode *root, TreeNode* p, TreeNode* q){
        if (root == NULL){
            return NULL;
        }
        
        if (root == p || root == q ){
            return root;
        } 
        
        TreeNode *left = NULL, *right = NULL;
        if (q->val < root->val){
            left = dfs(root->left, p, q);
        }else if (p->val > root->val){
            right = dfs(root->right, p, q);
        }else{
            return root;
        }
        
        if (left && right){
            return root;
        }else if (left != NULL){
            return left;
        }else{
            return right;
        }
    }
};

要回复问题请先登录注册

返回顶部