剑指 Offer 68 - II 二叉树的最近公共祖先

概述

https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

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

后续遍历

这次不再是 BST，因此我们只能自底向上来找，那自然是用后续遍历。

递归函数返回什么好呢？找到目标节点后自然是返回目标节点，否则的话：

1. 如果是 p 和 q，就返回 p 和 q，
2. 否则返回 nullptr。

注意处理 p 为 q 的父节点的情况。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return nullptr;
        auto l = lowestCommonAncestor(root->left, p, q);
        auto r = lowestCommonAncestor(root->right, p, q);
        if (l != nullptr && r != nullptr) {
            return root;
        } else if (l == nullptr && r == nullptr) {
            if (root == p || root == q) return root;
            else return nullptr;
        } else {
            if (root == p || root == q) return root;
            else return l == nullptr ? r : l;
        }
    }
};

Links: sword-offer-68-2

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