题目

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

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

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

思路

原有思路

  • 查询有两个子节点有两个目标节点的节点。
  • 然后查询当前节点的左右子节点，如果有一个子节点的子节点只包含一个目标节点，则他的父节点则为最近公共祖先。

改良后思路

  • 目标节点一定存在于当前树。
  • 中序遍历所有节点，如果当前接电接点或者其子节点匹配到了目标节点，则返回当前节点。
  • 如果当前节点的左右节点分别匹配到了一个目标节点（root == null || p || q 直接返回root），则当前节点是最近公共祖先。

    代码

原版代码

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
int leftFist(struct TreeNode* root, struct TreeNode* p, struct TreeNode*  q) {
    int ret = 0;
    if(root->left) {
        ret =  ret + leftFist(root->left, p, q);
    } 
    
    if(root->right){
        ret = ret+ leftFist(root->right, p, q);
    }
    if(root == p) {
        ret +=1;
    }
    if(root == q) {
        ret +=1;
    }
    return ret;
}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    struct TreeNode* retRoot = NULL ;
    int retSum =  leftFist(root, p, q);
    
    if(retSum ==  2) {
        int retSumleft = NULL;
        if(root->left) {
            retSumleft = leftFist(root->left, p, q);
        }
        if(0 < retSumleft &&  retSumleft < 2) {
            // printf("retSumleft:%d,", root->left->val);
            return root;
        }
        
        int retSumright = NULL;
        if(root->right) {
            retSumright = leftFist(root->right, p, q);
        }
        if(0 < retSumright && retSumright< 2) {
            // printf("retSumright:%d", root->right->val);
            return root;
        }
    }
    if(root->left) {
        retRoot =  lowestCommonAncestor(root->left, p, q);
        if(retRoot) {
            return retRoot;
        }
    } 
    
    if(root->right){
        retRoot =  lowestCommonAncestor(root->right, p, q);
        if(retRoot) {
            return retRoot;
        }
    }
    return retRoot;
}

c语言让我跑了1888ms。。

优化解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
   if(root == NULL || root == p || root == q) {
       return root;
   }
    struct TreeNode* left = lowestCommonAncestor(root->left, p ,q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p ,q);
    
    if(left == NULL && right == NULL) return NULL;
    if(left != NULL && right != NULL) return root;
    return (left == NULL ? right : left);
}

12ms