前言

最近的工作實(shí)在太忙，沒(méi)有充足的時(shí)間靜下心來(lái)總結(jié)一些系列的知識(shí)，所以這段時(shí)間就先碎片化的做些算法題，找找手感。

題目

https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/

給定一個(gè)根為 root 的二叉樹(shù)，每個(gè)節(jié)點(diǎn)的深度是 該節(jié)點(diǎn)到根的最短距離 。

如果一個(gè)節(jié)點(diǎn)在 整個(gè)樹(shù) 的任意節(jié)點(diǎn)之間具有最大的深度，則該節(jié)點(diǎn)是 最深的 。

一個(gè)節(jié)點(diǎn)的 子樹(shù) 是該節(jié)點(diǎn)加上它的所有后代的集合。

返回能滿足 以該節(jié)點(diǎn)為根的子樹(shù)中包含所有最深的節(jié)點(diǎn) 這一條件的具有最大深度的節(jié)點(diǎn)。

題目拆解

其實(shí)這道題題目描述的不太好，看了好久我才明白這題是啥意思。

其實(shí)本質(zhì)上，這道題就是要做兩件事，

• 第一件事，找到所有最深的節(jié)點(diǎn)，因?yàn)榇嬖诓⒘猩疃鹊那闆r，所以是找到所有最深的節(jié)點(diǎn)。
• 找到一個(gè)能把所有最深節(jié)點(diǎn)都包含到自己子樹(shù)里的最小的樹(shù)。

吶，就是這么兩件事。

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

• 找到所有的最深節(jié)點(diǎn)：深度優(yōu)先，給每一個(gè)節(jié)點(diǎn)和他的深度維護(hù)一個(gè)映射關(guān)系，最后排序得到一個(gè)最深的深度值。
• 找到一個(gè)把所有最深的節(jié)點(diǎn)都包含的子樹(shù)（詳細(xì)說(shuō)下這個(gè)）。

找到一個(gè)把所有最深的節(jié)點(diǎn)都包含的子樹(shù)

這個(gè)判斷起來(lái)其實(shí)也不復(fù)雜，大體來(lái)說(shuō)分為兩步，還是深度優(yōu)先。

• 看看最大深度是不是在自己子樹(shù)里？左子樹(shù)里還是右子樹(shù)里？還是都沒(méi)有？
• 然后判斷是返回自己？還是返回子樹(shù)？還是返回null？

然后再來(lái)解釋這個(gè)怎么判斷返回自己還是返回子樹(shù)，三種情況

• 如果最深節(jié)點(diǎn)不在自己這，返回null；
• 如果最深節(jié)點(diǎn)左右子樹(shù)都有，那就返回自己。
• 最深節(jié)點(diǎn)在左子樹(shù)里，返回左子樹(shù)，在右子樹(shù)里，返回右子樹(shù)。

好了要做的事情就這些?？梢詫?xiě)代碼了

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);
        // 第一次深度優(yōu)先,找到標(biāo)記所有節(jié)點(diǎn)的深度
        dfsFirst(root, null);

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

        // 第二次深度優(yōu)先,找到需要返回的子樹(shù)
        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;
        // 遇到最深節(jié)點(diǎn)了,返回自己.
        if (node2Deep.get(self) == maxDeep) return self;

        // 往下看看左右子樹(shù)里面有沒(méi)有最深節(jié)點(diǎn)
        // 注意這里只要返回不是null,就說(shuō)明包含最深節(jié)點(diǎn)
        TreeNode left = dfsSecond(self.left);
        TreeNode right = dfsSecond(self.right);

        // 第一種情況,說(shuō)明左右子樹(shù)都包含最深節(jié)點(diǎn),返回自己
        if (left != null && right != null) return self;
        // 第二種情況,左右哪邊有最深節(jié)點(diǎn),返回哪邊
        if (left != null) return left;
        if (right != null) return right;
        // 第三種情況,最深節(jié)點(diǎn)不在自己家,返回null
        return null;

    }

}

總結(jié)

刷leecode時(shí)，要認(rèn)真理解題意，比如這道題，就是把題目和示例看了好幾遍，才明白到底要干一個(gè)什么事。