LeetCode236. Lowest Common Ancestor of a Binary Tree 题解

题目链接：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/?tab=Description

思路：如果两个节点第一个在左子树中，一个在右子树中，那么他们的最近共同祖先就是root；如果两个节点都在左子树中，那么深度遍历时首先遇到的那个节点就是两节点的最近共同祖先；若两个都在右子树中，同理深度遍历时首先遇到的那个节点就是两节点的最近共同祖先。

Java代码如下：

public 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 root; return left == null ? right : left; } }