剑指 Offer 68 - II. 二叉树的最近公共祖先

题目描述

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

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

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

解题思路

  • 终止条件：
    • 当越过叶节点，则直接返回nullptr
    • 当root等于p或者q，则直接返回root
  • 递推工作：
    • 开启递归左子节点，返回值记为left
    • 开启递归右子节点，返回值记为right
  • 返回值，根据left和right，可展开为四种情况
    • 当left和right同时为空，说明root的左 / 右子树中都不包含p或q，返回nullptr
    • 当left和right同时不为空，说明p和q分列在root的异侧（分别在左/右子树），因此root为最近公共祖先，返回root
    • 当left为空，right不为空，有两种情况
      • p、q其中一个在右子树中，此时right指向p或q
      • p、q都在右子树中，此时right指向最近公共祖先即诶单
    • 当left不为空、right为空，同理

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)

知识点

二叉树，递归，DFS

代码

  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.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  13.         if(root == nullptr || root == p || root == q) return root;
  14.         TreeNode *left = lowestCommonAncestor(root->left, p, q);
  15.         TreeNode *right = lowestCommonAncestor(root->right, p, q);
  16.         if (!left && !right) {
  17.             return nullptr;
  18.         }
  19.         if(left == nullptr) return right;
  20.         if(right == nullptr) return left;
  21.         return root;
  22.     }
  23. };

参考资料

  1. DFS题解