力扣热门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; } }