- 38.4%

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/#/description

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

1 | tmp |

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.

https://discuss.leetcode.com/topic/18614/easy-c-recursive-and-iterative-solutions

Easy C++ Recursive and Iterative Solutions

方法一：

Well, remember to take advantage of the property of binary search trees, which is, node -> left -> val < node -> val < node -> right -> val. Moreover, both p and q will be the descendants of the root of the subtree that contains both of them. And the root with the largest depth is just the lowest common ancestor. This idea can be turned into the following simple recursive code.

1 | class Solution { |

我的代码实现：

1 | /** |

方法二：

Of course, we can also solve it iteratively.

1 | class Solution { |

方法三：

使用236的方法

1 | /** |

3 lines with O(1) space, 1-Liners, Alternatives

Just walk down from the whole tree’s root as long as both p and q are in the same subtree (meaning their values are both smaller or both larger than root’s). This walks straight from the root to the LCA, not looking at the rest of the tree, so it’s pretty much as fast as it gets. A few ways to do it:

Iterative, O(1) space

Python

1 | def lowestCommonAncestor(self, root, p, q): |

Java

1 | public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { |

(in case of overflow, I’d do (root.val - (long)p.val) * (root.val - (long)q.val))

Different Python

1 | def lowestCommonAncestor(self, root, p, q): |

“Long” Python, maybe easiest to understand

1 | def lowestCommonAncestor(self, root, p, q): |

Recursive

Python

1 | def lowestCommonAncestor(self, root, p, q): |

Python One-Liner

1 | def lowestCommonAncestor(self, root, p, q): |

Java One-Liner

1 | public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { |

“Long” Python, maybe easiest to understand

1 | def lowestCommonAncestor(self, root, p, q): |

https://discuss.leetcode.com/topic/22095/c-solution-40ms

C++ solution . 40ms

1 | /** |

https://discuss.leetcode.com/topic/18438/python-iterative-solution

Python Iterative Solution

1 | class Solution: |

https://discuss.leetcode.com/topic/19536/my-python-recursive-solution

My Python recursive solution

1 | class Solution: |