leetcode：236. 二叉树的最近公共祖先

题目

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

示例 1：
[中等] 236. 二叉树的最近公共祖先 - 图1

  1. 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
  2. 输出：3
  3. 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：
[中等] 236. 二叉树的最近公共祖先 - 图2

  1. 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
  2. 输出：5
  3. 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

  1. 输入：root = [1,2], p = 1, q = 2
  2. 输出：1

解答 & 代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     /* 递归函数定义：给定二叉树 root，返回节点 p 和 节点 q 的最近公共祖先
  13.        如果只有一个节点 p、q 中只有一个存在于二叉树 root 中，则返回那个节点
  14.        如果两个节点 p、q 都不在二叉树 root 中，则返回空 NULL*/
  15.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  16.         // 递归结束条件 1：如果根节点为空，说明节点 p、q 都不在该二叉树中，直接返回空
  17.         if(root == NULL)
  18.             return NULL;
  19.         // 递归结束条件 2：如果根节点 = 其中一个节点，则返回根节点
  20.         if(root == p || root == q)
  21.             return root;
  23.         // 递归处理左、右子树
  24.         TreeNode* left = lowestCommonAncestor(root->left, p, q);
  25.         TreeNode* right = lowestCommonAncestor(root->right, p, q);
  26.         // 后序位置
  27.         // 若两个节点 p、q 分别在左右子树中，则 root 就是最近公共祖先，返回 root
  28.         if(left != NULL && right != NULL)
  29.             return root;
  30.         // 若两个节点 p、q 都在左子树中，则返回 left
  31.         else if(left != NULL && right == NULL)
  32.             return left;
  33.         // 若两个节点 p、q 都在右子树中，则返回 right
  34.         else
  35.             return right;
  36.     }
  37. };

复杂度分析：设二叉树节点数为 N

  • 时间复杂度 O(N)：遍历二叉树每个节点
  • 空间复杂度 O(log N)：递归栈空间，取决于栈的深度

执行结果：

  1. 执行结果：通过
  3. 执行用时：12 ms, 在所有 C++ 提交中击败了94.39% 的用户
  4. 内存消耗：14.1 MB, 在所有 C++ 提交中击败了 23.34% 的用户