力扣热门100题之二叉树的最近公共祖先

一句话核心思路

递归遍历二叉树：

• 如果当前节点是p或q，直接返回它
• 去左子树找，去右子树找
• 如果左右都找到了→ 当前节点就是答案
• 如果只在左边找到→ 答案在左边
• 如果只在右边找到→ 答案在右边

完整代码实现：

/** * 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) { // 递归终止：空了 或 找到了p/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; } return left != null ? left : right; } }