# 二叉树最近公共祖先详解（LCA问题详解）

Lowest Common Ancestor of a Binary Tree 问题描述

Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

## 二叉搜索树 BST

• LCA(2,4) = 2
• LCA(0,5) = 2

• 两个值都在左边，则LCA在左边
• 两个值都在右边，则LCA在右边
• 一个在左一个在右，则说明LCA就是当前的root节点。

## 普通二叉树

• LCA(5,2) = 5
• LCA(5,1) = 3

Using a bottom-up approach, we can improve over the top-down approach by avoiding traversing the same nodes over and over again.

We traverse from the bottom, and once we reach a node which matches one of the two nodes, we pass it up to its parent. The parent would then test its left and right subtree if each contain one of the two nodes. If yes, then the parent must be the LCA and we pass its parent up to the root. If not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either p or q), or NULL (if both the left and right subtree does not contain either p or q) up.

Sounds complicated? Surprisingly the code appears to be much simpler than the top-down one.

from : http://articles.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

## 多次查询的普通二叉树

Tarjan算法基于DFS和并查集进行求解。

LCA(6,4) ,那么，由于是后续遍历，我们遍历到4的时候，6已经被访问过，且祖先设置为5，所以答案就是5 （后序遍历的是标志是否被访问~）

C++

## 参考资料

### 6 thoughts on “二叉树最近公共祖先详解（LCA问题详解）”

1. Wakingup says:

哇塞，厉害！

2. Diyue Xiao says:

感谢感谢！

3. congrt says:

Thanks for this post. Nice!

4. Jacob says:

我觉得你的网站看起来好舒服哦，想问一下这个code的这个format是怎么搞得啊？

• 哈哈，简洁优雅有木有~~~ 你说的是代码的那个框框嘛，插件：Crayon Syntax Highlighter