[leetcode]Lowest Common Ancestor of a Binary Search Tree

作者:luozhipeng   发表日期:2015-7-12  浏览:1,216次

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).”

lca

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.

 

题意:给定一个二叉搜索树(二叉排序树),求两个节点的最近公共祖先。

 

输入:根节点指针,另两个节点指针。

返回:最近公共祖先的指针。

 

思路:由于是二叉排序树,那么最近公共祖先的值一定两个节点之间,如两个节点的值分别是x,y,且x<y,最近公共祖先的值为z,那么z>=x && z<=y,由此我们只需从根节点开始遍历,当访问节点值z>y时就访问右子树,当访问节点z<x时就访问左子树,否则返回当前节点即可。


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

标签:

本文固定链接: http://www.luozhipeng.com/?p=401
转载请注明: luozhipeng 2015-7-12 于 罗志鹏的BLOG 发表

上一篇: :下一篇
评论:请安装多说插件!
返回顶部