知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 19 - 二叉树的最近公共祖先 ## 题目(LeetCode 236) 给定二叉树和两个节点 p、q,找到它们的最近公共祖先。 ## 解法:递归 ```java class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) return root; // p、q 分布两侧 return left != null ? left : right; } } ``` ## 复杂度 - 时间 O(n),空间 O(n) ## 一句话总结 后序遍历,左右子树都找到了就是当前节点,否则返回非空的那个。 ## 解法二:迭代(父指针法) 先用 BFS/DFS 记录每个节点的父节点,再用类似"两链表找交点"的方式找 LCA。 ```java class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { Map<TreeNode, TreeNode> parent = new HashMap<>(); Deque<TreeNode> stack = new ArrayDeque<>(); parent.put(root, null); stack.push(root); // 建立父指针表,直到 p 和 q 都找到 while (!parent.containsKey(p) || !parent.containsKey(q)) { TreeNode node = stack.pop(); if (node.left != null) { parent.put(node.left, node); stack.push(node.left); } if (node.right != null) { parent.put(node.right, node); stack.push(node.right); } } // 收集 p 的所有祖先 Set<TreeNode> ancestors = new HashSet<>(); while (p != null) { ancestors.add(p); p = parent.get(p); } // q 向上找第一个在祖先集合中的节点 while (!ancestors.contains(q)) q = parent.get(q); return q; } } ``` ## 解法对比 | | 解法一(递归) | 解法二(迭代+父指针) | |--|--------|--------| | 时间复杂度 | O(n) | O(n) | | 空间复杂度 | O(n) | O(n) | | 特点 | 简洁优雅,推荐 | 无递归栈溢出,逻辑更显式 |
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入