LeetCode 865 具有所有最深节点的最小子树 | 笔记

题目描述

给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。

返回包含原始树中所有最深节点的 最小子树 。

如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。

一个节点的子树是该节点加上它的所有后代的集合。

示例 1

输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：我们返回值为 2 的节点，在图中用黄色标记。在图中用蓝色标记的是树的最深的节点。注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。

思路

考虑到最深的节点可能有多个

首先考虑找到最深的叶子节点，可以用层序遍历找到所有最深的叶子节点
然后从这些最深的叶子节点开始，向上遍历，找到第一个公共祖先，这个公共祖先就是我们要找的最小子树的根节点
最后返回这个公共祖先作为结果

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        vector<int> fa(501, -1), dleves;
        vector<TreeNode*> mp(501, nullptr);
        queue<TreeNode*> q, tmp;
        q.push(root);
        while (!q.empty()) {
            int sz = q.size();
            dleves.clear();
            while (sz--) {
                TreeNode* p = q.front();
                q.pop();
                dleves.push_back(p->val);
                mp[p->val] = p;
                if (p->left){
                    q.push(p->left);
                    fa[p->left->val] = p->val;
                }
                if (p->right) {
                    q.push(p->right); 
                    fa[p->right->val] = p->val;
                }
            }
        }
        while (true) {
            int anc = dleves[0];
            bool ok = true;
            for (int i = 1; i < dleves.size(); ++i) {
                if (dleves[i] != anc) {
                    ok = false;
                    break;
                }
            }
            if (ok) return mp[anc];

            for (auto& v : dleves) {
                v = fa[v];
            }
        }
        return root;
    }
};

复杂度分析

时间复杂度： $O(n)$ ，其中 $n$ 是二叉树的节点数。需要进行一次层序遍历 $O(n)$ ，以及一次向上跳跃寻找公共祖先的过程 $O(logn)$ 。
空间复杂度： $O(n)$ ，其中 $n$ 是二叉树的节点数。需要存储二叉树每个节点的父亲节点，以及层序遍历的队列等等。

优化

这样虽然是很朴素的想法，但实际上不够直接，仔细思考发现：

最深子树的根节点意味着其左右子树的深度相同
答案一定在左子树或右子树中
可以用DFS来解决

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    pair<TreeNode*, int> dfs(TreeNode* p) {
        if (!p) return {nullptr, 0};

        auto [l, ln] = dfs(p->left);
        auto [r, rn] = dfs(p->right);
        if (ln > rn) return {l, ln+1};
        if (rn > ln) return {r, rn+1};
        return {p, ln+1}; 
    }
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).first;
    }
};

LeetCode 个人主页

leetcode.cn

kalev - 力扣（LeetCode）

View kalev’s profile on LeetCode, the world’s largest programming community.

https://leetcode.cn/u/kalev/