题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

样例描述

思路

递归 + 回溯

1. 本题在这里基础上少了BST的性质，就无法快速判断p、q结点在左子树还是右子树上。
2. 因此需要每次遍历两颗子树判断里面有没有p和q，最坏情况需要遍历所有的树，复杂度是O(n)。
3. 如果p，q分布在异侧，就返回根结点。
4. 如果碰到叶子结点就直接返回null。碰到root为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) {
          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) return right;
          if (right == null) return left;
          //两子树都为空，说明没有
          if (left == null && right == null)  return root;
          //如果left和right都不为空，说明p、q分布在左右两个子树
          return root;
    }
}