lowest-common-ancestor-of-a-binary-search-tree

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the <a href="https://en.wikipedia.org/wiki/Lowest_common_ancestor" target="_blank">definition of LCA on Wikipedia</a>: &ldquo;The lowest common ancestor is defined between two nodes <code>p</code> and <code>q</code> as the lowest node in <code>T</code> that has both <code>p</code> and <code>q</code> as descendants (where we allow a node to be a descendant of itself).&rdquo;

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/14/binarysearchtree_improved.png" style="width: 200px; height: 190px;" />
<pre>
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/14/binarysearchtree_improved.png" style="width: 200px; height: 190px;" />
<pre>
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
</pre>

Example 3:

<pre>
Input: root = [2,1], p = 2, q = 1
Output: 2
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the tree is in the range <code>[2, 105]</code>.</li>
	<li><code>-109 &lt;= Node.val &lt;= 109</code></li>
	<li>All <code>Node.val</code> are unique.</li>
	<li><code>p != q</code></li>
	<li><code>p</code> and <code>q</code> will exist in the BST.</li>
</ul>

lowestCommonAncestor

Lowest Common Ancestor of a Binary Search Tree

Lowest Common Ancestor of a Binary Tree

lowest-common-ancestor-of-a-binary-tree

二叉树的最近公共祖先

Smallest Common Region

smallest-common-region

最小公共区域

Lowest Common Ancestor of a Binary Tree II

lowest-common-ancestor-of-a-binary-tree-ii

二叉树的最近公共祖先 II

Lowest Common Ancestor of a Binary Tree III

lowest-common-ancestor-of-a-binary-tree-iii

二叉树的最近公共祖先 III

Lowest Common Ancestor of a Binary Tree IV

lowest-common-ancestor-of-a-binary-tree-iv

二叉树的最近公共祖先 IV

Tree

Depth-First Search

Binary Search Tree

Binary Tree

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

<a href="https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin" target="_blank">百度百科</a>中最近公共祖先的定义为：&ldquo;对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。&rdquo;

例如，给定如下二叉搜索树:&nbsp; root =&nbsp;[6,2,8,0,4,7,9,null,null,3,5]

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/binarysearchtree_improved.png" style="height: 190px; width: 200px;">

&nbsp;

示例 1:

<pre>输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 <code>2 </code>和节点 <code>8 </code>的最近公共祖先是 <code>6。</code>
</pre>

示例 2:

<pre>输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 <code>2</code> 和节点 <code>4</code> 的最近公共祖先是 <code>2</code>, 因为根据定义最近公共祖先节点可以为节点本身。</pre>

&nbsp;

说明:

<ul>
	<li>所有节点的值都是唯一的。</li>
	<li>p、q 为不同节点且均存在于给定的二叉搜索树中。</li>
</ul>