［LeetCode］Lowest Common Ancestor of a Binary Search Tree-白红宇

［LeetCode］Lowest Common Ancestor of a Binary Search Tree

阅读量：2236 次

发布时间：2019-05-09

本文共 1181 字，大约阅读时间需要 3 分钟。

思路：

利用二分搜索树的性质，当找到一个node，满足 ( p->val - node->val ) * ( q->val - node->val ) <= 0时，即说明p和q在node的两边，或者p与q有一个就是node

1，先决条件：p和q存在于BST上

2，不变式：先判断是否满足结束条件，然后再通过比较决定下一步进入左子树还是右子树（判断左右子树是否为空）；

3，结束条件：找到node满足 ( p->val - node->val ) * ( q->val - node->val ) <= 0

4，临界条件：root没有左右子树

// 顺利一遍过

/** * 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->left == NULL && root->right == NULL){            return NULL;        }        if ((p->val - root->val) * (q->val - root->val) <= 0 ){            return root;        }        if ( (p->val > root->val) && (q->val > root->val) ){            if (root->right != NULL)                return lowestCommonAncestor(root->right, p, q);            else                 return NULL;        }else if ( (p->val < root->val) && (q->val < root->val) ){            if (root->left != NULL)                return lowestCommonAncestor(root->left, p, q);            else                 return NULL;        }    }};

转载地址：http://hcpbb.baihongyu.com/

你可能感兴趣的文章