[LeetCode 866] Smallest Subtree with all the Deepest Nodes

題目

給定一個根為 root 的二叉樹，每個結點的深度是它到根的最短距離。

如果一個結點在整個樹的任意結點之間具有最大的深度，則該結點是最深的。

一個結點的子樹是該結點加上它的所有後代的集合。

傳回能滿足“以該結點為根的子樹中包含所有最深的結點”這一條件的具有最大深度的結點。

示例：

輸入：[3,5,1,6,2,0,8,null,null,7,4]
輸出：[2,7,4]
解釋：
           

我們傳回值為 2 的結點，在圖中用黃色标記。
在圖中用藍色标記的是樹的最深的結點。
輸入 "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" 是對給定的樹的序列化表述。
輸出 "[2, 7, 4]" 是對根結點的值為 2 的子樹的序列化表述。
輸入和輸出都具有 TreeNode 類型。
           

提示：

樹中結點的數量介于 1 和 500 之間。

每個結點的值都是獨一無二的。

解題思路

1. DFS，采用遞歸周遊；
2. 記錄最深的葉子結點的深度，周遊每個節點時判斷以該節點為根的子樹是否擁有最深的節點；
3. 遞歸計算目前節點的左右子樹的高度，如果高度一緻，則進行如下判斷：
   1. 如果目前節點深度最深，則說明是可能的結果，記錄該節點、節點深度，并标記擁有最深節點；
   2. 如果左右子樹都擁有最深節點，則說明該子樹為可能的結果，記錄該節點，并标記擁有最深節點；
   3. 如果目前節點深度與最深葉子節點深度一緻，則說明該節點也滿足條件，标記擁有最深節點；
4. 如果根節點的左右子樹高度一緻，則傳回根節點。

Code in C++

/**
 * 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 {
private:
    TreeNode* result;
    int maxDepth;

    int _GetLevel(TreeNode* root, int depth, bool &hasDeepst) {
        if (nullptr == root)
            return ;

        bool leftHasDeepst = false, rightHasDeepst = false;
        int leftLevel =  + _GetLevel(root->left, depth+, leftHasDeepst);
        int rightLevel =  + _GetLevel(root->right, depth+, rightHasDeepst);

        if (leftLevel == rightLevel) {
            if (depth > maxDepth) {
                result = root;
                maxDepth = depth;
                hasDeepst = true;
            } else if (leftHasDeepst && rightHasDeepst) {
                result = root;
                hasDeepst = true;
            } else if (depth == maxDepth) {
                hasDeepst = true;
            } 
        } else if (leftLevel > rightLevel) {
            hasDeepst = leftHasDeepst;
            return leftLevel;
        } else {
            hasDeepst = rightHasDeepst;
        }

        return rightLevel;
    }

public:

    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        result = nullptr;
        maxDepth = ;

        if (nullptr == root)
            return result;

        bool leftHasDeepst = false, rightHasDeepst = false;
        int leftLevel = _GetLevel(root->left, , leftHasDeepst);
        int rightLevel = _GetLevel(root->right, , rightHasDeepst);
        if (leftLevel == rightLevel)
            result = root;

        return result;
    }
};
           

效率

優化方案

• 采用非遞歸的先序周遊