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

Tag: 剑指-Offer Posted on 2022-02-28 11:36:24 Edited on 2022-02-28 11:54:23 Views: 283

概述

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;
        }
    }
};

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