LeetCode236 二叉树的最近公共祖先

发表于 | 分类于 |
字数统计: 322 | 阅读时长 ≈ 1

链接: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

题意

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

解法

有一种比较直观的想法是对于每个节点，判断它的左右子树是否分别包含p和q
但是这样就需要进行两次遍历 时间复杂度为N^2
需要进行优化

核心思想还是dfs
每次处理左节点和右节点
如果两者分别包含p或者q
则root一定是lca
否则返回左右节点中同时包含p和q的节点
优化后的代码十分简洁美丽

代码

原始做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool have(TreeNode* root, TreeNode* node) {
        if (!root) return false;
        if (root == node) return true;
        return have(root -> left, node) || have(root -> right, node);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        bool left = have(root -> left, p), right = have(root -> right, q);
        if ((left && right) || (!left && !right) || root == p || root == q) {
            return root;
        }
        if (left) {
            return lowestCommonAncestor(root -> left, p, q);
        }
        else {
            return lowestCommonAncestor(root -> right, p, q);
        }
    }
};

优化后

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return nullptr;
        if (root == p || root == q) return root;
        TreeNode* l = lowestCommonAncestor(root -> left, p, q);
        TreeNode* r = lowestCommonAncestor(root -> right, p, q);
        if (l && r) return root;
        return l ? l : r;
    }
};