拓展：最近公共祖先系列解题框架

1644. 二叉树的最近公共祖先 II https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-ii

1644. Lowest Common Ancestor of a Binary Tree II https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii

1650. 二叉树的最近公共祖先 III https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-iii

1650. Lowest Common Ancestor of a Binary Tree III https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii

1676. 二叉树的最近公共祖先 IV https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree-iv

1676. Lowest Common Ancestor of a Binary Tree IV https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iv

235. 二叉搜索树的最近公共祖先 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree

235. Lowest Common Ancestor of a Binary Search Tree https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree

236. 二叉树的最近公共祖先 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree

236. Lowest Common Ancestor of a Binary Tree https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 LCOF https://leetcode.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof

剑指 Offer 68 - II. 二叉树的最近公共祖先 https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof

剑指 Offer 68 - II. 二叉树的最近公共祖先 LCOF https://leetcode.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	Difficulty
1644. Lowest Common Ancestor of a Binary Tree II🔒	🟠
1650. Lowest Common Ancestor of a Binary Tree III🔒	🟠
1676. Lowest Common Ancestor of a Binary Tree IV🔒	🟠
235. Lowest Common Ancestor of a Binary Search Tree	🟠
236. Lowest Common Ancestor of a Binary Tree	🟠

Prerequisites

Before reading this article, you should learn:

• Basic Binary Tree Structure
• DFS/BFS Traversal of Binary Trees
• Dong's Guide to Binary Trees (Overview)

While written exams often feature challenging problems like dynamic programming and backtracking, interviews tend to focus on more classic and practical questions with moderate difficulty.

This article introduces a classic algorithm problem using Git: the Lowest Common Ancestor (LCA).

We frequently use the git pull command, which by default merges remote changes into our local repository using the merge method. If we use git pull -r, it employs the rebase method to integrate remote changes.

The most apparent difference between these methods is that merge results in a branch with many "forks," whereas rebase produces a linear branch. Regardless of the method, if conflicts exist, Git detects them and prompts you to resolve them manually.

So, how does Git determine if two branches have conflicts?

Taking the rebase command as an example, consider the scenario below where I am on the dev branch and execute git rebase master. The dev branch will then be attached on top of the master branch:

Here's what Git does:

First, it finds the Lowest Common Ancestor (LCA) of the two branches. Then, starting from the master node, it replays the commits from LCA to dev. If these changes conflict with the commits from LCA to master, Git prompts you to resolve the conflicts manually. The final result is that the dev branch is fully integrated onto the master branch.

So, how does Git find the LCA of two different branches? This is a classic algorithm problem, and I will explain it step by step from the basics.

Finding an Element

Solve Five Problems in Seconds

236. Lowest Common Ancestor of a Binary Tree

1676. Lowest Common Ancestor of a Binary Tree IV

1644. Lowest Common Ancestor of a Binary Tree II

235. Lowest Common Ancestor of a Binary Search Tree

1650. Lowest Common Ancestor of a Binary Tree III

loading...