首页 > 代码库 > Leetcode 235

Leetcode 235

思路1:对于一棵二叉排序树

1.如果当前节点的值小于p,q的值,那么LCA一定在root的右边;

2.如果当前节点的值大于p,q的值,那么LCA一定在root的左边;

3.如果当前节点的值在p,q的值之间,那么当前节点为LCA;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root->val<p->val&&root->val<q->val)
            return lowestCommonAncestor(root->right,p,q);
        else if(root->val>p->val&&root->val>q->val)
            return lowestCommonAncestor(root->left,p,q);
        else return root;
    }
};

思路2:直接搜索两个数p,q的值,记录下搜索过程的路径,左侧为-1,右侧为1.比对路径即可,路径开始不同的点即为LCA(即交叉点)

思路3:对于一棵二叉排序树,如果p,q均在当前节点左字树或者右子树,则根节点与p,q的值的差值同号,乘积大于零。

          然后继续判断在左边还是在右边

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    while((root->val-p->val)*(root->val-q->val)>0){
        if(root->val-p->val>0)
            root=root->left;
        else 
            root=root->right;
    }
    return root;
}

 

Leetcode 235