Leetcode — 865. Smallest Subtree with all the Deepest Nodes (中文)

問題連結: https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/

給予一個二元樹的根節點 root , 各節點的深度depth即代表這個節點到根節點的最短距離

回傳這個二元樹中, 包含樹中所有最深的節點的最小子樹, 而我們在這邊指的最深的節點代表的是這個節點在這個二元樹中, 離根節點的距離最遠

範例:

Photo credit to Leecode

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
解釋: 我們會回傳2(圖中黃色節點)當作我們的最終答案, 因為範例的這棵樹有兩個最深節點, 因此我們會回傳2,也就是這兩個最深節點的最小的共同父節點

想法:

所以我們也可把題目解釋成, 我們要回傳樹中最深的節點, 但如果有超過一個以上的最深節點, 我們就要一次就要回傳有包含這些目標節點的最小子樹
(你也可以說我們要找這些最深節點的最小共同祖父節點, 總之概念都相同, 看你怎樣解讀題目會讓你更理解題目就好)

我的想法就是將一層一層的走訪整個樹, 我們可以利用每個節點的高度height來縮小可能結果的答案節點範圍, 或者更白話文一點 - 我們利用每個節點它們從自己到他們可到的葉節點的最遠距離

👷Difference between a HEIGHT and a DEPTH: 
1. 通常講depth of a node, 代表的是從根節點到現在節點的距離, 因此最深節點就有最高的深度, 而根節點的深度則是0
2. 而講到height of a node, 則有點相反, 代表的是從現在節點到它可以到達的最遠葉節點(且為它自己的子節點)的距離, 任一葉節點的height都是0
▶️▶️ 總結: 當我們講這些節點都在同一層的時候, 其實就在講這些節點就在同個深度(depth), 但同一層的節點們不一定會有相同高度(height)! 

來利用例子來看我怎麼發現我們可以用高度來縮小答案節點的範圍

假設我們有下面這三種樹:

Example Trees

在上述圖中, 我用橘色代表我們最終需要回傳的正確節點, 也就是我們符合條件最小子樹的根節點, 我還在每個節點旁邊都標示好各節點的高度, 這樣我們更容易看出什麼答案節點的"規律"

你可以發現, 一個節點的高度越高, 代表它離最深節點越遠, 所以當我們找到一個節點的高度 比跟他同層的所有節點們都還要高的時候, 代表這個節點可以幫助我們找到這個二元樹中最深的節點, 因此, 我們這時候就可以在這層的時候拋棄這個節點以外的節點們,進而縮小我們最終答案的範圍了,

程式邏輯:

那我們來看我們如何利用上述提到的特點寫成程式碼 —

因為我們決定要一層接一層的走訪樹, 我們將會把我們待會要走訪的節點放進佇列queue裡面, 但記得, 我們並不是真的會把在樹裡面的所有節點都放進佇列中, 我們會忽略那些height比較低的節點們

雖然概念是這樣, 但其實我們在每層至多也只會選一個節點而已, 因為真的也至多一個節點的高度 高於其他節點

也許你會說, 不對啊 我自己畫的某個樹圖的時候, 同一層有兩個節點的高度 比同層的其他節點都還要高, 那要怎麼選?
但其實不用擔心這件事, 因為我們在每層都只選一個節點走下去的關係, 因此下一層節點至多也只有兩個節點讓我們選, 因此兩個節點高度的比較, 頂多也只有一個高度比較高, 或者兩者高度一樣高的結果

所以我們在每層做的事情就是決定接下來要繼續走訪的下一個節點, 我們將會比較 現在節點的左節點跟右節點 各別的高度:

1. 若兩節點的高度一樣: 則代表現在這個節點就是我們最終的答案了, 因為這兩個節點皆有在這個樹中最深的葉節點
2. 若我們可以得出某節點的高度比較高: 則這個節點可能是最深節點或者最深節點(們)的父節點, 因為我們還不確定這是最終答案還是最終答案的父節點, 我們就把它放進佇列裡, 作為我們下層拜訪的節點, 而在這層另一個在這邊高度比較矮的節點就會被我們遺棄

以下為 0ms 的程式碼, 贏過 100% —

public TreeNode subtreeWithAllDeepest(TreeNode root) {
        if(root.left==null && root.right==null)
            return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty())
        {
            TreeNode node = queue.poll();
            int leftH = height(node.left, 0);
            int rightH = height(node.right, 0);
            if(leftH == rightH)
                return node;
            if(leftH > rightH) //abandon the right node
                queue.offer(node.left);
            else 
                queue.offer(node.right);
        }
        return null;
    }
    //distance from node to leaf node
    public int height(TreeNode node, int count){
        if(node==null)
            return count-1;
        int leftH = height(node.left, count+1);
        int rightH = height(node.right, count+1);
        return Math.max(leftH, rightH);
    }

因為其實我們queue裡面每次也都只放一個節點, 因此我們也可以直接用一個TreeNode變數來代替queue的存在:

public TreeNode subtreeWithAllDeepest(TreeNode root) {
        TreeNode node = root;
        while(node!=null)
        {
            int leftH = height(node.left, 0);
            int rightH = height(node.right, 0);
            if(leftH == rightH)
                return node;
            if(leftH > rightH)
                node = node.left;
            else 
                node = node.right;
        }
        return null;
    }
    public int height(TreeNode node, int count){
        if(node==null)
            return count-1;
        int leftH = height(node.left, count+1);
        int rightH = height(node.right, count+1);
        return Math.max(leftH, rightH);
    }