Keshawn_lu's Blog

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

字数统计: 542阅读时长: 2 min
2020/05/10 Share

题目简介:

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

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

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

示例 1:

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

示例 2:

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

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉树中。

思路:

​ 从根节点遍历,递归搜索。

​ 递归终止条件:当前节点为空或等于p或q,则返回当前节点。最后会有两种情况:

  1. p,q处于同一子树下,即左右结点均不为空,如:

    1
    2
    3
      5
    / \
    p q

    此时返回root,即它们的最近公共祖先为5

  2. p,q不处于同一子树下,如:

    1
    2
    3
    4
    5
        5
    / \
    p 2
    / \
    2 q

    此时搜索5的右子树返回的为空,搜索5的左子树返回的为p(搜索到p时会直接返回,不会再继续搜索下去了),所以返回不为空的结点即可,即最近公共祖先为p。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* 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 == NULL || root == p || root == q)
return root;

TreeNode* left = lowestCommonAncestor(root -> left, p, q);
TreeNode* right = lowestCommonAncestor(root -> right, p, q);

if(left && right){
//p,q在同一子树下的情况
return root;
}

return left ? left : right; //p,q不在同一子树下的情况

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: