865. 具有所有最深節點的最小子樹

思路

要找到滿足這個條件的最深節點：「一個節點，所有以它為祖的葉節點都是整棵樹的最深節點」

用dfs找到最深的深度，中途順便找答案，
假如一個節點的左樹跟右樹一樣深，而且都是最深，那麼這個節點就被列入參考選項。

拿題目範例舉例，左樹會找到最深的兩個節點7，4，mxHeight = 3，節點2是答案。
找到右邊的1，左邊高度等於右邊高度，但深度不是最深，所以1不會將2覆蓋掉。

若根結點的左右子樹相反，會先找到1滿足條件，
因為0跟8的深度都等於那時更新到一半的最深深度mxHeight。
但到後面時更新mxHeight，發現2滿足條件，覆蓋掉1。

第二種寫法將使用到的變數放到函數呼叫當中，
若左樹的深度大於右樹，答案節點一定在左樹，
若右樹的深度大於左樹，答案節點一定在右樹，
如果相等，那麼當前節點就是答案。

程式碼

1. dfs

class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        int mxHeight = 0;
        TreeNode* res;
        auto dfs = [&](this auto&&dfs, TreeNode* node, int height) -> int {
            if(!node) {
                mxHeight = max(mxHeight, height);
                return height;
            }
            int left = dfs(node->left, height + 1);
            int right = dfs(node->right, height + 1);
            if(left == right && left == mxHeight) {
                res = node;
            }
            return max(left, right);
        };
        dfs(root, 0);
        return res;
    }
};

2. dfs

class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        auto dfs = [&](this auto&&dfs, TreeNode* node) -> pair<int, TreeNode*> {
            if(!node) return {0, nullptr};
            auto [leftDepth, leftNode] = dfs(node->left);
            auto [rightDepth, rightNode] = dfs(node->right);
            if(leftDepth > rightDepth) return {leftDepth + 1, leftNode};
            if(rightDepth > leftDepth) return {rightDepth + 1, rightNode};
            return {leftDepth + 1, node}; // leftDepth == rightDepth
        };
        return dfs(root).second;
    }
};

複雜度分析

• 時間複雜度：$O(n)$，$n$ 是節點數量
• 空間複雜度：$O(1)$，遞迴調用占用系統的系統棧空間 $O(\log{n} ~ n)$