相信刷过二叉树的人，一定遇到过最近公共祖先的问题；如果没有遇到过，你一定是个假的刷题人 hhhhhh
废话不多说，直接上题：
首选这个题目使用的是递归，那么就要搞清楚递归的四要素
- 当前节点：root
- 该做什么：判断当前节点和要寻找的两个节点的大小关系
- 什么时候做：先序遍历
- 返回值：最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return null; // 始终保持 p.val < q.val if (p.val > q.val) return lowestCommonAncestor(root, q, p); // 如果 p 和 q 恰好在当前节点的两侧，那么当前就是最近公共祖先 if (p.val <= root.val && q.val >= root.val) return root; // 如果 p 和 q 均大于 root，则去右孩子找 else if (p.val > root.val) return lowestCommonAncestor(root.right, p, q); // 如果 p 和 q 均小于 root，则去左孩子找 else return lowestCommonAncestor(root.left, p, q);}该题较上一题的区别就是没有二叉搜索树的特性，其他的不变
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return null; // 刚刚进入时的处理 // 如果当前节点等于 p||q，那么当前节点就是最近公共祖先 // 原因：因为是先序遍历刚刚进入，所以一定可以保证当前节点的上方是不存在 p||q 的 if (root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); // 说明 p q 在当前节点的左右两边，一边一个，所以最近公共祖先就是 root if (left != null && right != null) return root; // 说明以当前节点为根的子树中不存在 p q if (left == null && right == null) return null; // 说明 p q 存在于左孩子或右孩子中 // 至于为什么可以保证是最近的公共祖先，这就要得益于后序遍历的特点 // 后序遍历是从下往上开始离开节点，所以可以得到最近的公共祖先 return left == null ? right : left;}private TreeNode res = null;// 记录每个节点的深度private Map<Integer, Integer> depth = new HashMap<>();public TreeNode lcaDeepestLeaves(TreeNode root) { maxDepth(root); return lcaDeepestLeavesHelper(root);}private TreeNode lcaDeepestLeavesHelper(TreeNode root) { if (root == null) return null; // 说明是叶子节点 // 有此判断是因为下面要获得 root.left.val & root.right.val // 如果 root.left == null || root.right == null 那么 root.left.val 会空指针异常 if (root.left == null && root.right == null) return root; // 说明只有一个孩子，当前节点肯定不是最深叶子节点的最近公共祖先，故递归非空孩子节点 if (root.left == null || root.right == null) return root.left == null ? lcaDeepestLeavesHelper(root.right) : lcaDeepestLeavesHelper(root.left); // 获得左右子树的深度 // 如果深度相同，那么当前节点就是最近公共祖先 // 如果深度不同，那么最近公共祖先在深度更大的一边 int leftDepth = depth.get(root.left.val); int rightDepth = depth.get(root.right.val); if (leftDepth == rightDepth) return root; else if (leftDepth > rightDepth) return lcaDeepestLeavesHelper(root.left); else return lcaDeepestLeavesHelper(root.right);}private int maxDepth(TreeNode root) { if (root == null) return 0; int left = maxDepth(root.left); int right = maxDepth(root.right); depth.put(root.val, Math.max(left, right) + 1); return Math.max(left, right) + 1;}
综上所述，主要是需要判断何时才是最近公共祖先