前言

最近的工作实在太忙，没有充足的时间静下心来总结一些系列的知识，所以这段时间就先碎片化的做些算法题，找找手感。

题目

leetcode-cn.com/problems/sm…

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

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

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

返回能满足 以该节点为根的子树中包含所有最深的节点 这一条件的具有最大深度的节点。

题目拆解

其实这道题题目描述的不太好，看了好久我才明白这题是啥意思。

其实本质上，这道题就是要做两件事，

• 第一件事，找到所有最深的节点，因为存在并列深度的情况，所以是找到所有最深的节点。
• 找到一个能把所有最深节点都包含到自己子树里的最小的树。

呐，就是这么两件事。

所以题目拆解完了，该怎么做也就知道了。

• 找到所有的最深节点：深度优先，给每一个节点和他的深度维护一个映射关系，最后排序得到一个最深的深度值。
• 找到一个把所有最深的节点都包含的子树（详细说下这个）。

找到一个把所有最深的节点都包含的子树

这个判断起来其实也不复杂，大体来说分为两步，还是深度优先。

• 看看最大深度是不是在自己子树里？左子树里还是右子树里？还是都没有？
• 然后判断是返回自己？还是返回子树？还是返回null？

然后再来解释这个怎么判断返回自己还是返回子树，三种情况

• 如果最深节点不在自己这，返回null；
• 如果最深节点左右子树都有，那就返回自己。
• 最深节点在左子树里，返回左子树，在右子树里，返回右子树。

好了要做的事情就这些。可以写代码了

class Solution {

    private Map<TreeNode, Integer> node2Deep = new HashMap<>();
    private int maxDeep;


    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        node2Deep = new HashMap<>();
        maxDeep = -1;
        node2Deep.put(null, -1);
        // 第一次深度优先,找到标记所有节点的深度
        dfsFirst(root, null);

        // 遍历找到最深的深度
        for (Integer value : node2Deep.values()) {
            maxDeep = Math.max(value, maxDeep);
        }

        // 第二次深度优先,找到需要返回的子树
        return dfsSecond(root);


    }

    void dfsFirst(TreeNode self, TreeNode parent) {
        if (self == null) return;
        node2Deep.put(self, node2Deep.get(parent) + 1);
        dfsFirst(self.left, self);
        dfsFirst(self.right, self);
    }

    TreeNode dfsSecond(TreeNode self) {
        // 走到头了,返回null
        if (self == null) return self;
        // 遇到最深节点了,返回自己.
        if (node2Deep.get(self) == maxDeep) return self;

        // 往下看看左右子树里面有没有最深节点
        // 注意这里只要返回不是null,就说明包含最深节点
        TreeNode left = dfsSecond(self.left);
        TreeNode right = dfsSecond(self.right);

        // 第一种情况,说明左右子树都包含最深节点,返回自己
        if (left != null && right != null) return self;
        // 第二种情况,左右哪边有最深节点,返回哪边
        if (left != null) return left;
        if (right != null) return right;
        // 第三种情况,最深节点不在自己家,返回null
        return null;

    }

}

总结

刷leecode时，要认真理解题意，比如这道题，就是把题目和示例看了好几遍，才明白到底要干一个什么事。

本文正在参与「掘金 2021 春招闯关活动。