LeetCode 「中等」236.二叉树的最近公共祖先
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
示例
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
输入：root = [1,2], p = 1, q = 2
输出：1
解答
DFS（深度优先搜索）
关键思路
对于根节点 root，p 和 q 的分布有两种可能：
p和q分居root的左右子树，则 LCA 为rootp和q存在于root的同一侧子树中，就变成规模小一点的相同问题
具体步骤
定义递归函数
递归函数：返回当前子树中 p 和 q 的 LCA。如果没有 LCA，就返回 null
从根节点 root 开始往下递归遍历：
- 如果遍历到
p或q，比方说p，则 LCA 要么是当前的p（q在p的子树中），要么是p之上的节点（q不在p的子树中），不可能是p之下的节点，不用继续往下走，返回当前的p - 当遍历到
null节点，空树不存在p和q，没有 LCA，返回 null - 当遍历的节点
root不是p或q或null，则递归搜寻root的左右子树- 如果左右子树的递归都有结果，说明
p和q分居root的左右子树，返回root - 如果只是一个子树递归调用有结果，说明
p和q都在这个子树，返回该子树递归结果 - 如果两个子树递归结果都为
null，说明p和q都不在这两个子树中，返回null
- 如果左右子树的递归都有结果，说明
Code
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
const dfs = (node) => {
// 如果当前节点为空，返回 null
if (!node) return null;
// 如果当前节点是 p 或 q，返回当前节点
if (node === p || node === q) return node;
const left = dfs(node.left);
const right = dfs(node.right);
// 如果左右子树都找到了 p 或 q，说明当前节点是 LCA
if (left && right) return node;
// 如果只在左子树中找到 p 或 q，返回左子树的结果
if (left) return left;
// 如果只在右子树中找到 p 或 q，返回右子树的结果
if (right) return right;
// 如果左右子树都没有找到 p 或 q，返回 null
return null;
};
return dfs(root);
};