day138-LeetCode 235. Lowest Common Ancestor of a Binary Search

题目

LeetCode 235. Lowest Common Ancestor of a Binary Search
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.

分析

注意这颗是中序遍历的二叉树,左子树节点值小于根节点值小于右子树节点值。

题解

function lowestCommonAncestor (root, p, q) {
while(true){
let value = root.val
if(p.val >= value && value >= q.val || p.val <= value && value <= q.val){
return root
} else if(p.val > value && q.val > value){
root = root.right
} else {
root = root.left
}
}
}
文章作者: lmislm
文章链接: http://lmislm.com/2019/05/30/2019-05-30/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LMISLMのBlog