LeetCode 236 Lowest Common Ancestor of a Binary Tree

Tag: 二叉树 LeetCode Posted on 2022-02-07 23:57:04 Edited on 2022-02-08 00:30:37 Views: 160

概述

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

注意子节点没有父指针哦。

递归法

根节点肯定是其共同祖先,一直向下直到子节点都不是共同祖先。

好了,现在我们要如何判断子节点是否是共同祖先?只能递归了。

要注意节点本身也是其父节点。

递归套递归,时间复杂度爆炸。

class Solution {
public:
    TreeNode* ans;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        helper(root, p, q);
        return ans;
    }
    
    void helper(TreeNode* root, TreeNode* p, TreeNode* q) {
        ans = root;
        if (isCommonAncestor(root->left, p, q)) {
            helper(root->left, p, q);
        }
        if (isCommonAncestor(root->right, p, q)) {
            helper(root->right, p, q);
        }
    }
    
    bool isCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return isAncestor(root, p) && isAncestor(root, q);
    }
    
    bool isAncestor(TreeNode* root, TreeNode* p) {
        if (!root) return false;
        if (root == p) return true;
        if (root->left == p || root->right == p) return true;
        return isAncestor(root->left, p) || isAncestor(root->right, p);
    }
};

一个可以优化的地方是,对判断节点是否是 p 和 q 的祖先节点可以做一下缓存。

更加直接的递归法

https://mp.weixin.qq.com/s/9RKzBcr3I592spAsuMH45g

从下往上看,从 p 出发,将其父节点做标记,q 同理,则自下向上第一个有双重标记的节点即最近共同祖先。

那要怎么自下向上嘞?后续遍历!

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return nullptr;
        if (root == p || root == q) return root;
        auto l = lowestCommonAncestor(root->left, p, q);
        auto r = lowestCommonAncestor(root->right, p, q);
        
        if (l != nullptr && r != nullptr) {  // both are marked, which means root is a common ancestor
            return root;
        }
        if (l == nullptr && r == nullptr) {  // which means root is not ancestor of both nodes
            return nullptr;
        }
        return l ? l : r;  // root is only a ancestor of one of them, we should mark root
    }
};

这个递归函数的返回值有两种,因此不好理解。

其实可以这样理解,前期用作布尔值,后期兼顾用来传递结果。

这也是为啥我们不能随便 return 一个非 null 值来进行标记。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/