236. 二叉树的最近公共祖先

Problem: 236. 二叉树的最近公共祖先

[TOC]

思路

我们需要得到祖先节点,也就是说先遍历子节点再遍历父节点,后序遍历可以做到这一点,对于从子节点判断父节点的题目都可以用后序遍历。

返回条件,找到了p q或为nullptr,返回该节点,在处理中间节点时,我们收集左右节点的结果,如果都不为空则在左右子树上找到了p q,我们可以返回该节点。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q)
            return root; // 有效返回条件
        // 后序遍历
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        // 中间节点
        if (left == nullptr && right == nullptr) return nullptr;
        if (left == nullptr) return right;
        if (right == nullptr) return left;
        return root;
    }
};