题目概览给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”示例 1输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1输出3解释节点5和节点1的最近公共祖先是节点3 。示例 2输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4输出5解释节点5和节点4的最近公共祖先是节点5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3输入root [1,2], p 1, q 2输出1提示树中节点数目在范围[2, 10^5]内。-10^9 Node.val 10^9所有Node.val互不相同。p ! qp和q均存在于给定的二叉树中。来源236. 二叉树的最近公共祖先 - 力扣LeetCode解题分析方法一前序遍历根据前序遍历根-左-右的特性进行遍历我们只需要知道左右节点是否有 p 或 q 即可那么如果当前节点为空返回空。如果当前节点有一个等于 p 或 q 的节点就返回当前节点。如果左右节点返回的节点一个等于 p 且 另一个等于 q就返回当前根节点。由于我们是从左边最底层叶子节点开始遍历的这里的根节点一定是最小的。如果左右节点返回的节点有一个不为空返回该节点时间复杂度O(n)空间复杂度O(n)/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root null) { return null; } if (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 null; } if (left ! null right ! null) { return root; } return left ! null ? left : right; } }方法二哈希 记录父节点可以用哈希map存储所有节点和它父节点的映射然后再定义一个哈希集合 set 存储 p 的所有父节点然后遍历 q 的父节点当父节点再 p 的父节点集合中时返回该父节点即可。时间复杂度O(n)空间复杂度O(n)/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */ class Solution { MapInteger, TreeNode map new HashMap(); public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { dfs(root, null); SetInteger set new HashSet(); while(p ! null) { set.add(p.val); p map.get(p.val); } while(q ! null) { if (set.contains(q.val)) { return q; } q map.get(q.val); } return null; } public void dfs(TreeNode node, TreeNode parent) { if (node null) { return; } map.put(node.val, parent); dfs(node.left, node); dfs(node.right, node); } }
