二叉树的最近公共祖先

题面

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 树中节点数目在范围 [2, 105] 内。
• -109 <= Node.val <= 109
• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

分析

• 分类讨论

  flowchart TD
      A["开始：检查当前节点"] --> B{"当前节点状态?"}
      
      %% 第一层判断分支
      B -->|空节点| C["返回当前节点"]
      B -->|是节点 p| C
      B -->|是节点 q| C
      B -->|其它情况| D["递归查找左子树<br/>递归查找右子树"]
      
      %% 其它情况的第二层判断
      D --> E{"查找结果?"}
      E -->|左右子树都找到| F["返回当前节点"]
      E -->|只有左子树找到| G["返回左子树查找结果"]
      E -->|只有右子树找到| H["返回右子树查找结果"]
      E -->|左右子树都没找到| I["返回空节点"]
      
      %% 结束节点汇总
      C --> J["结束"]
      F --> J
      G --> J
      H --> J
      I --> J
      
      %% 样式优化（可选）
      classDef decision fill:#f9f,stroke:#333,stroke-width:2px
      classDef process fill:#9ff,stroke:#333,stroke-width:2px
      classDef endnode fill:#9f9,stroke:#333,stroke-width:2px
      class B,E decision
      class A,D process
      class C,F,G,H,I,J endnode

• lowestCommonAncestor 函数的返回值是什么意思？

  • 返回值的准确含义是「最近公共祖先的候选项」。对于最外层的递归调用者来说，返回值是最近公共祖先的意思
  • 但是，在递归过程中，返回值可能是最近公共祖先，也可能是空节点（表示子树内没找到任何有用信息）、节点 p 或者节点 q（可能成为最近公共祖先，或者用来辅助判断上面的某个节点是否为最近公共祖先）

• 为什么发现当前节点是 p 或者 q 就不再往下递归了？万一下面有 q 或者 p 呢？

  • 如果下面有 q 或者 p，那么当前节点就是最近公共祖先，直接返回当前节点
  • 如果下面没有 q 和 p，那既然都没有要找的节点了，也不需要递归，直接返回当前节点

• 代码实现

  /**
   * Definition for a binary tree node.
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   * };
   */
  class Solution {
  public:
      TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
          if (root == q || root == p || root == NULL)
              return root;
          TreeNode* left = lowestCommonAncestor(root->left, p, q);
          TreeNode* right = lowestCommonAncestor(root->right, p, q);
          if (left != NULL && right != NULL)
              return root;
          if (left == NULL)
              return right;
          return left;
      }
  };