[LeetCode]235.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）

代码

/*---------------------------------------
*   日期：2015-07-14
*   作者：SJF0115
*   题目: 235.Lowest Common Ancestor of a Binary Search Tree
*   网址：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;

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 == nullptr || p == nullptr || q == nullptr){
            return nullptr;
        }//if
        return helper(root,p,q);
    }
private:
    TreeNode* helper(TreeNode* root,TreeNode* p,TreeNode* q){
        if(root == nullptr || p == nullptr || q == nullptr){
            return nullptr;
        }//if
        int pVal = p->val;
        int qVal = q->val;
        int rootVal = root->val;
        // 分居两侧
        if((pVal <= rootVal && qVal >= rootVal) || (pVal >= rootVal && qVal <= rootVal)){
            return root;
        }//if
        // 左侧
        if(pVal < rootVal && qVal < rootVal){
            return helper(root->left,p,q);
        }//if
        // 右侧
        if(pVal > rootVal && qVal > rootVal){
            return helper(root->right,p,q);
        }//if
    }
};

int main(){
    Solution s;
    TreeNode* root = new TreeNode(6);
    TreeNode* node1 = new TreeNode(0);
    TreeNode* node2 = new TreeNode(9);
    TreeNode* node3 = new TreeNode(2);
    TreeNode* node4 = new TreeNode(3);
    TreeNode* node5 = new TreeNode(4);
    TreeNode* node6 = new TreeNode(5);
    TreeNode* node7 = new TreeNode(7);
    TreeNode* node8 = new TreeNode(8);
    root->left = node3;
    root->right = node8;
    node3->left = node1;
    node3->right = node5;
    node5->left = node4;
    node5->right = node6;
    node8->left = node7;
    node8->right = node2;
    TreeNode* node = s.lowestCommonAncestor(root,node3,node4);
    if(node != nullptr){
        cout<<node->val<<endl;
    }//if
    else{
        cout<<"nullptr"<<endl;
    }//else
    return 0;
}

运行时间

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>