<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by 可愛小松鼠 Cute Squirrel on Medium]]></title>
        <description><![CDATA[Stories by 可愛小松鼠 Cute Squirrel on Medium]]></description>
        <link>https://medium.com/@cutesciuridae?source=rss-59c68f365a24------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*Y3LO-_aKMS2VgDa_IkDdhA.png</url>
            <title>Stories by 可愛小松鼠 Cute Squirrel on Medium</title>
            <link>https://medium.com/@cutesciuridae?source=rss-59c68f365a24------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 03:41:50 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@cutesciuridae/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[字串應用題 是否為子序列? Is Subsequence Leetcode #392]]></title>
            <link>https://medium.com/@cutesciuridae/%E5%AD%97%E4%B8%B2%E6%87%89%E7%94%A8%E9%A1%8C-%E6%98%AF%E5%90%A6%E7%82%BA%E5%AD%90%E5%BA%8F%E5%88%97-is-subsequence-leetcode-392-ad330b58d732?source=rss-59c68f365a24------2</link>
            <guid isPermaLink="false">https://medium.com/p/ad330b58d732</guid>
            <category><![CDATA[subsequence]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[double-pointer]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[可愛小松鼠 Cute Squirrel]]></dc:creator>
            <pubDate>Fri, 22 Sep 2023 03:25:40 GMT</pubDate>
            <atom:updated>2023-09-22T03:25:40.957Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*penuLc8YdS4BNHHc.jpg" /></figure><p>這題的題目在這裡:</p><p><a href="https://leetcode.com/problems/is-subsequence/description?envType=daily-question&amp;envId=2023-09-22">LeetCode - The World&#39;s Leading Online Programming Learning Platform</a></p><p>題目會給定我們兩個字串，一個字串s，另一個字串t</p><p>要求我們判段<strong>字串s是否為字串t的子序列</strong>?<br>(也就是s的每個字元都可以在t裡面找到，而且前後相對順序相同)</p><p>測試範例:</p><p><strong>Example 1:</strong></p><pre>Input: s = &quot;abc&quot;, t = &quot;ahbgdc&quot;<br>Output: true</pre><p><strong>Example 2:</strong></p><pre>Input: s = &quot;axc&quot;, t = &quot;ahbgdc&quot;<br>Output: false</pre><p>約束條件:</p><p><strong>Constraints:</strong></p><ul><li>0 &lt;= s.length &lt;= 100</li><li>0 &lt;= t.length &lt;= 104</li><li>s and t consist only of lowercase English letters.</li></ul><p><strong>Follow up:</strong> Suppose there are lots of incoming s, say s1, s2, ..., sk where k &gt;= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?</p><p>演算法:</p><p>同樣使用到<strong>雙指針</strong>的技巧，一個從s的頭部開始，另一個從t的頭部開始。</p><p><strong>從左到右開始掃描，一次掃描一個字元</strong>，</p><p>比對s[i] 和 t[j] 是否相同，</p><p>如果<strong>相同</strong>，則i++，j++ 一起往右一格。</p><p>如果<strong>不同</strong>，則i不動，j++。</p><p>最後，掃描結束時，如果<strong>i = 字串s的長度</strong>，代表s的每個字元都可以在t裡面找到，而且前後相對順序相同。也就是說，<strong>字串s是字串t的子序列</strong>。</p><p>程式碼:</p><pre>class Solution:<br>    def isSubsequence(self, s: str, t: str) -&gt; bool:<br>  <br>        # two-pointers, one for s, the other for t<br>        idx_s, idx_t = 0, 0<br>  <br>        len_s, len_t = len(s), len(t)<br>        <br>        # linear scan from head<br>        while idx_s &lt; len_s and idx_t &lt; len_t:<br>            <br>            if s[idx_s] == t[idx_t]:<br>                # matched one character<br>                # s go to next position<br>                idx_s += 1<br>            <br>            # t go to next position<br>            idx_t += 1<br><br>        # check all character of s are matched<br>        return idx_s == len_s</pre><p>時間複雜度:</p><p>O( m + n ) 最大就是字串的長度，當idx_s或idx_t有一個率先抵達終點，則比對流程結束。</p><p>空間複雜度:</p><p>O(1) 使用到一組雙指針idx_s和idx_t，都是固定尺寸的臨時變數，占用的記憶體空間為常數級別O(1)</p><p>Reference:</p><p>[1] <a href="https://leetcode.com/problems/is-subsequence/solutions/678455/several-python-sol-sharing-w-comment/?envType=daily-question&amp;envId=2023-09-22">Several python sol sharing [w/ Comment] — Is Subsequence — LeetCode</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ad330b58d732" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[雙指針應用題 : Leetcode #11 Container With Most Water]]></title>
            <link>https://medium.com/@cutesciuridae/%E9%9B%99%E6%8C%87%E9%87%9D%E6%87%89%E7%94%A8%E9%A1%8C-leetcode-11-container-with-most-water-9ce0dac5c904?source=rss-59c68f365a24------2</link>
            <guid isPermaLink="false">https://medium.com/p/9ce0dac5c904</guid>
            <category><![CDATA[cointain-water]]></category>
            <category><![CDATA[double-pointer]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[optimization]]></category>
            <category><![CDATA[greedy]]></category>
            <dc:creator><![CDATA[可愛小松鼠 Cute Squirrel]]></dc:creator>
            <pubDate>Wed, 20 Sep 2023 13:01:49 GMT</pubDate>
            <atom:updated>2024-07-31T16:49:21.234Z</atom:updated>
            <content:encoded><![CDATA[<h3>雙指針應用題 : Leetcode #11 <a href="https://leetcode.com/problems/container-with-most-water/">Container With Most Water</a></h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*RwkBOhN9O8seVQcV.jpg" /></figure><p>這題的題目在這裡:</p><p><a href="https://leetcode.com/problems/container-with-most-water/description">LeetCode - The World&#39;s Leading Online Programming Learning Platform</a></p><p>題目會給定一個陣列，分別代表每個隔板的高度，請問，最多可以儲存多少水在水槽中?</p><p>請看下方範例圖解，直觀好懂。</p><p>(註: 不用擔心水不夠，可以假定水量無限制供應)</p><p>測試範例:</p><p><strong>Example 1:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/801/0*bPiJZLpBgFqRIexl.jpg" /></figure><pre>Input: height = [1,8,6,2,5,4,8,3,7]<br>Output: 49<br>Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.</pre><p><strong>Example 2:</strong></p><pre>Input: height = [1,1]<br>Output: 1</pre><p>約束條件:</p><p><strong>Constraints:</strong></p><ul><li>n == height.length</li><li>2 &lt;= n &lt;= 105</li><li>0 &lt;= height[i] &lt;= 104</li></ul><p>演算法:</p><p><strong>關鍵點</strong>在於，<strong>水槽能裝的水量</strong>，<strong>由隔板比較矮的那一端</strong>決定。</p><p>因此，我們只要建立一個滑窗，初始化是寬度最大值，每次收縮比較矮的一邊，</p><p>如果左邊的隔板比右邊矮，就收縮左邊。</p><p>如果右邊的隔板比左邊矮，就收縮右邊。</p><p>每次<strong>迭代的時候</strong>，同步更新當下<strong>可以儲存的水量的最大值</strong><br>(相當於二維平面上投影的面積，就像範例圖中的樣子)</p><p>最後，取面積最大值，就是答案。</p><p>程式碼:</p><pre>class Solution:<br>    def maxArea(self, height: List[int]) -&gt; int:<br>        <br>        # length of input array<br>        size = len(height)<br>        <br>        # two pointers, left init as 0, right init as size-1<br>        left, right = 0, size-1<br>        <br>        # maximal width between leftmost stick and rightmost stick<br>        max_width = size - 1<br>        <br>        # area also known as the amount of water<br>        area = 0<br>        <br>        # trade-off between width and height<br>        # scan each possible width and compute maximal area<br>        for width in range(max_width, 0, -1):<br>            <br>            if height[left] &lt; height[right]:<br>                # the height of lefthand side is shorter<br>                area = max(area, width * height[left] )<br>                <br>                # update left index to righthand side<br>                left += 1<br>                <br>            else:<br>                # the height of righthand side is shorter<br>                area = max(area, width * height[right] )<br>                <br>                # update right index to lefthand side<br>                right -= 1<br>                <br>        return area</pre><p>時間複雜度:</p><p>O( n ) 收縮滑窗，寬度從n-1 收縮到 1，總共耗費O(n)的時間</p><p>空間複雜度:</p><p>O(1) 都是臨時變數，所占用的記憶體空間固定，都是常數級別O(1)</p><p>Reference:</p><p>[1] <a href="https://leetcode.com/problems/container-with-most-water/solutions/1069698/python-js-go-c-o-n-by-two-pointers-w-comment/">Python/JS/Go/C++ O(n) by two-pointers [w/ Comment] — Container With Most Water — LeetCode</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9ce0dac5c904" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[滑動窗口應用題 Minimum Operations to Reduce X to Zero Leetcode #1658]]></title>
            <link>https://medium.com/@cutesciuridae/%E6%BB%91%E5%8B%95%E7%AA%97%E5%8F%A3%E6%87%89%E7%94%A8%E9%A1%8C-minimum-operations-to-reduce-x-to-zero-leetcode-1658-b51e6bead2cb?source=rss-59c68f365a24------2</link>
            <guid isPermaLink="false">https://medium.com/p/b51e6bead2cb</guid>
            <category><![CDATA[two-pointers]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[sliding-windows]]></category>
            <category><![CDATA[math]]></category>
            <dc:creator><![CDATA[可愛小松鼠 Cute Squirrel]]></dc:creator>
            <pubDate>Wed, 20 Sep 2023 04:45:09 GMT</pubDate>
            <atom:updated>2023-09-20T07:51:39.052Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*rOgUEq_2R1EWQ537.png" /></figure><p>這題題目在這裡:</p><p><a href="https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/description">LeetCode - The World&#39;s Leading Online Programming Learning Platform</a></p><p>題目會給定我們一個陣列，還有一個整數值x</p><p>問我們每次從<strong>陣列頭部</strong>或<strong>尾部</strong>取一個整數，最少需要幾次才能使取出的整數<strong>總和</strong>為x?</p><p>測試範例:</p><p><strong>Example 1:</strong></p><pre>Input: nums = [1,1,4,2,3], x = 5<br>Output: 2<br>Explanation: The optimal solution is to remove the last two elements to reduce x to zero.</pre><p><strong>Example 2:</strong></p><pre>Input: nums = [5,6,7,8,9], x = 4<br>Output: -1</pre><p><strong>Example 3:</strong></p><pre>Input: nums = [3,2,20,1,1,3], x = 10<br>Output: 5<br>Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.</pre><p>演算法:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1012/1*EgEp44KHNetHLAkzc3RJ1A.png" /></figure><p>維護一個滑窗，令滑窗的目標值為 sum( nums ) — x = 陣列總和 — x</p><p>則 <strong>藍色部分</strong>(滑窗內的元素和) + <strong>綠色部分</strong>(題目原本所求) <br>= (<strong>陣列總和</strong> — x) + x<br>= <strong>陣列總和</strong> = sum(nums)</p><p>題目所求為 <strong>湊到x的最小次數</strong>，相當於</p><p>Sliding window 內總和為 sum( nums ) — x ，伴隨著<strong>最大的滑窗長度</strong>。</p><p>最後， <strong>湊到x的最小次數 = len(nums) — 最大的滑窗長度</strong></p><p>程式碼:</p><pre>class Solution:<br>    def minOperations(self, nums: List[int], x: int) -&gt; int:<br>        <br>        # Min operation to meet x<br>        # &lt;=&gt; Max operation to meet sum(nums) - x<br>        target = sum(nums) - x<br><br>        if target &lt; 0:<br>            # Quick response for no solution<br>            return -1<br><br>        # left boundary of sliding window<br>        left = 0<br><br>        # summation of sliding window<br>        summation = 0<br><br>        # max length of sliding window whose sum is equal to ( sum(nums) - x )<br>        max_len = -1<br><br>        # Use sliding window to maximize window length, whose sum is equal to ( sum(nums) - x )<br>        for right, val in enumerate( nums ):<br>            <br>            summation += val<br><br>            while summation &gt; target:<br>                summation -= nums[left]<br>                left += 1<br><br>            if summation == target:<br>                cur_len = right - left + 1<br>                max_len = max(max_len, cur_len)<br><br>        # We cannot find interval sum = ( sum(nums) - x ), so no solution<br>        if max_len == -1:<br>            return max_len<br><br>        # Min operation to meet x<br>        # &lt;=&gt; Max operation to meet sum(nums) - x        <br>        return len(nums) - max_len</pre><p>時間複雜度:</p><p>O( n ) 成本耗費在滑動窗口 sliding window的拓展</p><p>空間複雜度:</p><p>O( 1 ) 使用到的都是臨時變數，占用記憶體空間是固定常數級別O( 1 )</p><p>Reference:</p><p>[1]<a href="https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/solutions/4066623/python-o-n-by-sliding-window-w-visualization/"> Minimum Operations to Reduce X to Zero — LeetCode</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b51e6bead2cb" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[經典演算法 陣列排序 Sort an Array Leetcode #912]]></title>
            <link>https://medium.com/@cutesciuridae/%E7%B6%93%E5%85%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E9%99%A3%E5%88%97%E6%8E%92%E5%BA%8F-sort-an-array-leetcode-912-386ddeab1924?source=rss-59c68f365a24------2</link>
            <guid isPermaLink="false">https://medium.com/p/386ddeab1924</guid>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[merge-sort]]></category>
            <category><![CDATA[sort-an-array]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[可愛小松鼠 Cute Squirrel]]></dc:creator>
            <pubDate>Tue, 19 Sep 2023 15:10:31 GMT</pubDate>
            <atom:updated>2023-09-21T06:41:05.493Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*8KOOjUnU2-VrhBg7.jpg" /></figure><p>題目在這裡:</p><p><a href="https://leetcode.com/problems/sort-an-array/description">LeetCode - The World&#39;s Leading Online Programming Learning Platform</a></p><p>這題就是經典的考排序驗算法，不管在教科書、上機考、面試白板題都是一個很基本又滿熱門的題目。</p><p>測試範例:</p><p><strong>Example 1:</strong></p><pre>Input: nums = [5,2,3,1]<br>Output: [1,2,3,5]<br>Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).</pre><p><strong>Example 2:</strong></p><pre>Input: nums = [5,1,1,2,0,0]<br>Output: [0,0,1,1,2,5]<br>Explanation: Note that the values of nums are not necessairly unique.</pre><p>約束條件:</p><p><strong>Constraints:</strong></p><ul><li>1 &lt;= nums.length &lt;= 5 * 104</li><li>-5 * 104 &lt;= nums[i] &lt;= 5 * 104</li></ul><p>演算法:</p><p>題目已經明言規定不可以呼叫程式語言或者平台內建的sort function，就是要求我們真正實作一個upper bound為O( n log n)的排序演算法。</p><p>考慮到退化的關係，QuickSort會在最差情況會退到O( n^2 )。</p><p>註: 退化的意思就是，Worst case發生在當所有element 都已經排好，或者逆序排好，或者陣列元素都相同的時候。</p><p>所以本題我們選擇Merge Sort來實作，Merge sort 即使在最差情況 worst case依然能保障O( n log n)的complexity upper bound 。</p><p>程式碼:</p><pre>class Solution:<br>    def sortArray(self, nums: List[int]) -&gt; List[int]:<br>        <br>        # Use divide and conquer strategy with mergesort<br>        def mergeSort(left, right):<br><br>            if left &gt;= right:<br>                # only one element, no need to sort<br>                # invalid interval, no need to sort<br>                return<br>            <br>            # Divide :<br>            mid = left + (right - left) // 2<br>            mergeSort( left , mid  )<br>            mergeSort( mid+1, right)<br><br><br>            # Conquer, also known as merge<br>            a, b = left, mid+1<br>            merging = []<br>            <br>            # Two way merge between left half and right half<br>            while a &lt;= mid and b &lt;= right:<br><br>                if nums[a] &lt; nums[b]:<br>                    merging.append( nums[a] )<br>                    a += 1<br>                else:<br>                    merging.append( nums[b] )<br>                    b += 1<br><br>            # Only left half remains<br>            while a &lt;= mid:<br>                merging.append( nums[a] )<br>                a += 1<br><br>            # Only right half remains<br>            while b &lt;= right:<br>                merging.append( nums[b] )<br>                b += 1<br><br>            # Write back to originally specific interval<br>            nums[left : right+1] = merging<br><br>            return</pre><p>時間複雜度:</p><p>O( n log n)，至多 log n 層，每層merge又耗費O(n)去合併左半部和右半部子陣列。</p><p>空間複雜度:</p><p>O( n ) 合併時耗費O(n)的輔助空間去儲存merge完的結果</p><p>Reference:</p><p>[1] <a href="https://leetcode.com/problems/sort-an-array/solutions/4064124/python-o-n-log-n-by-merge-sort/">Python O( n log n) by merge sort — Sort an Array — LeetCode</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=386ddeab1924" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[經典圖論面試題 Validate Binary Search Tree Leetcode #98]]></title>
            <link>https://medium.com/@cutesciuridae/%E7%B6%93%E5%85%B8%E9%9D%A2%E8%A9%A6%E9%A1%8C-validate-binary-search-tree-leetcode-98-7a6b34b3134e?source=rss-59c68f365a24------2</link>
            <guid isPermaLink="false">https://medium.com/p/7a6b34b3134e</guid>
            <category><![CDATA[monotone-increasing]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[binary-search-tree]]></category>
            <category><![CDATA[dfs]]></category>
            <category><![CDATA[recursion]]></category>
            <dc:creator><![CDATA[可愛小松鼠 Cute Squirrel]]></dc:creator>
            <pubDate>Tue, 19 Sep 2023 07:46:28 GMT</pubDate>
            <atom:updated>2024-01-01T12:09:29.515Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*b23T1jNTyZobF20P.jpg" /></figure><p>題目在這裡:</p><p><a href="https://leetcode.com/problems/validate-binary-search-tree/description">LeetCode - The World&#39;s Leading Online Programming Learning Platform</a></p><p>題目會給定一顆二元樹的根結點，要求我們驗證這一顆樹是否為合法的二元搜索樹，也就是所謂的Binary search tree, aka BST?</p><p>題目也給了BST的定義:</p><ol><li>所有<strong>左子樹的節點</strong>的值都<strong>小於 根節點</strong>的值</li><li>所有<strong>右子樹的節點</strong>的值都<strong>大於 根節點</strong>的值</li><li>所有左子樹和右子樹的分支也都遵循相同的規則。</li></ol><p>測試範例:</p><p><strong>Example 1:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/302/0*ZFTsYlm__mbW6rhx.jpg" /></figure><pre>Input: root = [2,1,3]<br>Output: true</pre><p><strong>Example 2:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/422/0*JCys5TuVDa_ym24t.jpg" /></figure><pre>Input: root = [5,1,4,null,null,3,6]<br>Output: false<br>Explanation: The root node&#39;s value is 5 but its right child&#39;s value is 4.</pre><p>演算法:</p><p>其實這題有很多種解法，但是剛好<strong>二元搜索樹</strong>有一個<strong>單調遞增的性質</strong>。</p><p>也就是說，如果使用前面提過的inorder traversal拜訪整顆樹，那拜訪的軌跡剛好會從小到大排列。</p><p>因此，我們可以先給定一個<strong>上、下邊界</strong>，分別是(<strong>最小正整數</strong>, <strong>最大正整數</strong>)來包住<strong>整顆樹的合理值的範圍</strong>，接著不斷<strong>依照當下節點的值</strong>，<strong>動態更新</strong>對應的<strong>(下區間，上區間)</strong>，最後遞迴檢查左子樹和右子樹。</p><p>假如過程中發現有一個節點的值超出合理範圍，就return False，代表這顆樹不是合法的BST。</p><p>假如全部檢查完，所有節點都落在合理範圍，就return True，代表這顆樹是合法的BST。</p><p>程式碼:</p><pre>class Solution:<br>    def isValidBST(self, root: TreeNode) -&gt; bool:<br>        <br>        # Use maximal system integer to represent infinity<br>        INF = sys.maxsize<br>        <br>        def helper(node, lower, upper):<br>            <br>            if not node:<br>                # empty node or empty tree<br>                return True<br>            <br>            if lower &lt; node.val &lt; upper:<br>                # check if all tree nodes follow BST rule<br>                return helper(node.left, lower, node.val) and helper(node.right, node.val, upper)<br>            <br>            else:<br>                # early reject when we find violation<br>                return False<br>            <br>        # ----------------------------------<br>        <br>        return helper( node=root, lower=-INF, upper=INF )</pre><p>時間複雜度:</p><p>O( n ) 從根節點，依循DFS框架，拜訪整顆樹，每個節點最多拜訪一次。</p><p>空間複雜度:</p><p>O(n) 成本耗費在遞迴呼叫時建立的call stack，最深的深度至多可為O(n)，當整顆樹向左歪斜，或者向右歪斜時。</p><p>Reference:</p><p>[1] <a href="https://leetcode.com/problems/validate-binary-search-tree/solutions/974147/python-js-java-go-c-o-n-by-dfs-and-rule-w-hint/">Python/JS/Java/Go/C++ O(n) by DFS and rule [w/ Hint] — Validate Binary Search Tree — LeetCode</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7a6b34b3134e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[陣列與圖論綜合應用題 Find the Duplicate Number Leetcode #287]]></title>
            <link>https://medium.com/@cutesciuridae/%E9%99%A3%E5%88%97%E8%88%87%E5%9C%96%E8%AB%96%E7%B6%9C%E5%90%88%E6%87%89%E7%94%A8%E9%A1%8C-find-the-duplicate-number-leetcode-287-951972621786?source=rss-59c68f365a24------2</link>
            <guid isPermaLink="false">https://medium.com/p/951972621786</guid>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[find-the-duplicate-number]]></category>
            <category><![CDATA[cycle-detection]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[floyd-algorithm]]></category>
            <dc:creator><![CDATA[可愛小松鼠 Cute Squirrel]]></dc:creator>
            <pubDate>Tue, 19 Sep 2023 03:04:46 GMT</pubDate>
            <atom:updated>2023-09-19T03:04:46.639Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*_kZHYt1pWL8xawiI.png" /></figure><p>這題的題目在這裡:</p><p><a href="https://leetcode.com/problems/find-the-duplicate-number/description?envType=daily-question&amp;envId=2023-09-19">LeetCode - The World&#39;s Leading Online Programming Learning Platform</a></p><p>題目會給我們一個輸入陣列，長度為n+1。</p><p>陣列裡面會有n+1個數字，數字的範圍從1到n</p><p>裡面恰好有一個數字重複出現，要求我們找出那個重複的數字。</p><p>題目要求只能使用<strong>常數空間O(1)</strong>，並且限制<strong>不能</strong>修改陣列內容。</p><p>測試範例:</p><p><strong>Example 1:</strong></p><pre>Input: nums = [1,3,4,2,2]<br>Output: 2</pre><p><strong>Example 2:</strong></p><pre>Input: nums = [3,1,3,4,2]<br>Output: 3</pre><p>約束條件:</p><p><strong>Follow up:</strong></p><ul><li>How can we prove that at least one duplicate number must exist in nums?</li><li>Can you solve the problem in linear runtime complexity?</li></ul><p>演算法:</p><p>除了使用傳統的雙層搜索之外，</p><p>還可以使用圖論中的<strong>Cycle detection演算法</strong>來尋找<strong>重複的數字</strong>。</p><p>若我們把陣列<strong>每個位置</strong>想成一個<strong>節點</strong>。</p><p><strong>陣列內部的值</strong>，代表<strong>一條邊指向下一個節點</strong>的位置。</p><p>則<strong>環路Cycle的起點</strong>，就對應到陣列中<strong>重複出現的數字</strong>。</p><p>以範例一為例:</p><p>Input:<br>nums = [1,3,4,2,2]</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1000/0*CbzMjCoSDdbscbA6.png" /></figure><p>重複的數字是2</p><p>同時，二號節點，也是圖中環路Cycle的起點位置。</p><p>程式碼:</p><pre>class Solution:<br>    def findDuplicate(self, nums: List[int]) -&gt; int:<br>        <br>        # start hopping from Node_#0<br>        slow, fast = 0, 0<br>  <br>        # for locating start node of cycle<br>        check = 0<br>        <br>        # Step_#1<br>        # Cycle detection<br>        # Let slow jumper and fast jumper meet somewhere in the cycle <br>  <br>        while True:<br>            <br>             # slow jumper hops 1 step, while fast jumper hops two steps forward.<br>            slow = nums[ slow ]<br>            fast = nums[ nums[fast] ]<br>            <br>            if slow == fast:<br>                break<br>        <br>  <br>        # Step_#2<br>        # Locate the start node of cycle (i.e., the duplicate number)<br>        while True:<br>            <br>            slow = nums[ slow ]<br>            check = nums[ check ]<br>            <br>            if slow == check:<br>                break<br>        <br>        return check</pre><p>時間複雜度:</p><p>O(n) 整個陣列掃描至多兩遍</p><p>空間複雜度:</p><p>O(1) 耗費在slow, fast, check等臨時變數上，占用的記憶體空間皆固定O(1)，不會隨著問題規模放大而成長。</p><p>Reference:</p><p>[1] <a href="https://leetcode.com/problems/find-the-duplicate-number/solutions/515872/python-js-java-go-c-o-1-aux-space-by-hopping-w-hint/?envType=daily-question&amp;envId=2023-09-19">Python/JS/Java/Go/C++ O(1) aux space by hopping. [ w/ Hint ] — Find the Duplicate Number — LeetCode</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=951972621786" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[經典圖論面試題 Invert Binary Tree Leetcode #226]]></title>
            <link>https://medium.com/@cutesciuridae/%E7%B6%93%E5%85%B8%E5%9C%96%E8%AB%96%E9%9D%A2%E8%A9%A6%E9%A1%8C-invert-binary-tree-leetcode-226-4846194d03ae?source=rss-59c68f365a24------2</link>
            <guid isPermaLink="false">https://medium.com/p/4846194d03ae</guid>
            <category><![CDATA[invert-binary-tree]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[dfs]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[graph]]></category>
            <dc:creator><![CDATA[可愛小松鼠 Cute Squirrel]]></dc:creator>
            <pubDate>Mon, 18 Sep 2023 14:49:03 GMT</pubDate>
            <atom:updated>2023-09-18T14:49:03.919Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*f7vQqUiW_4QUwjax.jpg" /></figure><p>這題的題目在這裡</p><p><a href="https://leetcode.com/problems/invert-binary-tree/description">LeetCode - The World&#39;s Leading Online Programming Learning Platform</a></p><p>題目會給我們一顆二元樹的根節點，要求我們對齊根節點正中央的虛擬分割線，反轉整顆二元樹。</p><p>測試範例:</p><p><strong>Example 1:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/911/0*0FcGYkGFnV98WgTO.jpg" /></figure><pre>Input: root = [4,2,7,1,3,6,9]<br>Output: [4,7,2,9,6,3,1]</pre><p><strong>Example 2:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/761/0*_RKbYJFcQQAPZEPt.jpg" /></figure><pre>Input: root = [2,1,3]<br>Output: [2,3,1]</pre><p><strong>Example 3:</strong></p><pre>Input: root = []<br>Output: []</pre><p>約束條件:</p><p><strong>Constraints:</strong></p><ul><li>The number of nodes in the tree is in the range [0, 100].</li><li>-100 &lt;= Node.val &lt;= 100</li></ul><p>演算法:</p><p>利用DFS<strong>遞迴探索整顆樹</strong>的性質，來進行<strong>鏡像反轉</strong>。</p><ol><li>先交換左子樹和右子樹(在程式碼中，就是交換root.left 和 root.right)</li><li>遞迴處理下一層(這邊我們使用DFS 比較簡潔)</li><li>返回樹根root，樹根本身保持不動。</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/972/0*--Fa013Vp3oGpKUY.png" /></figure><p>程式碼:</p><pre>class Solution:<br>    def invertTree(self, root: TreeNode) -&gt; TreeNode:<br>        <br>        if root:<br>            # General case:<br>            <br>            # invert child node of current root<br>            root.left, root.right = root.right, root.left<br>            <br>            # invert subtree with DFS<br>            self.invertTree( root.left )<br>            self.invertTree( root.right )<br>            <br>            return root<br>        <br>        else:<br>            # Base case:<br>            # empty tree<br>            <br>            return None</pre><p>時間複雜度:</p><p>O( n ) 每個節點最多拜訪一次。</p><p>空間複雜度:</p><p>O( n ) 空間成本耗費在遞迴呼叫時所建立的call stack，</p><p>最深的那一層在最後一層，當樹向左歪斜或向右歪斜時，<br>最深的深度可以到O( n )</p><p>Reference:</p><p>[1] <a href="https://leetcode.com/problems/invert-binary-tree/solutions/664132/python-js-java-go-c-o-n-by-dfs-w-visualization/">Python/JS/Java/Go/C++ O(n) by DFS [w/ Visualization] — Invert Binary Tree — LeetCode</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4846194d03ae" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[BFS 經典入門題 Binary Tree Level Order Traversal II Leetcode #107]]></title>
            <link>https://medium.com/@cutesciuridae/bfs-%E7%B6%93%E5%85%B8%E5%85%A5%E9%96%80%E9%A1%8C-binary-tree-level-order-traversal-ii-leetcode-102-8d0dde2b6b9?source=rss-59c68f365a24------2</link>
            <guid isPermaLink="false">https://medium.com/p/8d0dde2b6b9</guid>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[binary-tree]]></category>
            <category><![CDATA[fb]]></category>
            <category><![CDATA[queue]]></category>
            <category><![CDATA[level-order-traversal]]></category>
            <dc:creator><![CDATA[可愛小松鼠 Cute Squirrel]]></dc:creator>
            <pubDate>Mon, 18 Sep 2023 13:23:48 GMT</pubDate>
            <atom:updated>2023-09-20T08:16:39.963Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*FdihO6PagBUi_6LG.jpg" /></figure><p>這題的題目在這</p><p><a href="https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description">LeetCode - The World&#39;s Leading Online Programming Learning Platform</a></p><p>題目會給定給我們一顆二元樹的根結點，要求我們輸出<strong>上下顛倒</strong>的Level-order traversal的拜訪結果。</p><p>(基本上，就是<a href="https://leetcode.com/problems/n-ary-tree-level-order-traversal">前一題</a>的小改版。 XD)</p><p>測試範例:</p><p><strong>Example 1:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/277/0*VfGbY7SKCtKAnIok.jpg" /></figure><pre>Input: root = [3,9,20,null,null,15,7]<br>Output: [[15,7],[9,20],[3]]</pre><p><strong>Example 2:</strong></p><pre>Input: root = [1]<br>Output: [[1]]</pre><p><strong>Example 3:</strong></p><pre>Input: root = []<br>Output: []</pre><p>約束條件:</p><p><strong>Constraints:</strong></p><ul><li>The number of nodes in the tree is in the range [0, 2000].</li><li>-1000 &lt;= Node.val &lt;= 1000</li></ul><p>演算法:</p><p>和前一題一樣，這題就剛好可以套用圖論裡面的BFS廣度優先探索演算法，也呼應之前我們在<a href="https://medium.com/@cutesciuridae/%E5%9C%96%E8%AB%96graph-theory%E5%B8%B8%E7%94%A8%E7%9A%84%E5%B9%BE%E5%80%8B%E6%BC%94%E7%AE%97%E6%B3%95%E7%9A%84%E6%AF%94%E8%BC%83-216e85042133">圖論演算法統整</a>介紹過的概念。</p><p>BFS在探索Tree/Binary tree相關的領域中，還有一個名字，叫做<strong>Level-order traversal 逐層探索演算法</strong>。<strong>從第一層</strong>Root根接點，<strong>逐層探索</strong>到Leaf葉子節點 也是<strong>最深的那一層</strong>。</p><p>唯一的差別是，<strong>這題要求的是上下顛倒的順序</strong>。</p><p>所以，我們只要套用前一題的演算法，最後把結果做反向，再輸出，就滿足題目所求。</p><p>這種<strong>演算法化簡的技巧</strong>，在演算法理論也稱之為<strong>Reduction</strong>，</p><p>把一個<strong>新的問題A</strong>，映射到一個<strong>已經知道解法(演算法)的問題B</strong>，再透過已知問題B的解答<strong>反推問題A的答案</strong>。</p><p>程式碼:</p><pre>lass Solution:<br>    def levelOrderBottom(self, root: Optional[TreeNode]) -&gt; List[List[int]]:<br>    <br>        def levelOrder(root: TreeNode) -&gt; List[List[int]]:<br>        <br>        <br>            if not root:<br>                # Quick response for empty tree<br>                return []<br><br>            traversalQ, result = deque([root]), []<br><br>            # level order traversal<br>            while traversalQ:<br><br>                # going down level-by-level<br>                cur_level_trace, cur_level_len = [], len(traversalQ)<br>                for _ in range(cur_level_len):<br><br>                    cur_node = traversalQ.popleft()<br><br>                    cur_level_trace.append(cur_node.val)<br>                    if cur_node.left: traversalQ.append( cur_node.left )<br>                    if cur_node.right: traversalQ.append( cur_node.right )<br><br><br>                result.append( cur_level_trace )<br><br>            return result<br>        <br>        #-----------------------------------<br>        <br>        # Reduce to Leetcode #102 Binary tree level order traversal<br>        <br>        return levelOrder(root)[::-1]</pre><p>時間複雜度:</p><p>O( n ) 每個節點最多拜訪一次。</p><p>空間複雜度:</p><p>O( n ) 最深的那一層在最後一層，最長為O( n/2 )</p><p>[1] <a href="https://leetcode.com/problems/binary-tree-level-order-traversal-ii/solutions/2698400/python-java-js-c-go-by-normal-traversal-reduction-w-hint/">Python/Java/JS/C++/Go by normal traversal // Reduction [w/Hint] — Binary Tree Level Order Traversal II — LeetCode</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8d0dde2b6b9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[BFS 經典入門題 Binary Tree Level Order Traversal Leetcode #102]]></title>
            <link>https://medium.com/@cutesciuridae/bfs-%E7%B6%93%E5%85%B8%E5%85%A5%E9%96%80%E9%A1%8C-binary-tree-level-order-traversal-leetcode-102-102d900a9a9e?source=rss-59c68f365a24------2</link>
            <guid isPermaLink="false">https://medium.com/p/102d900a9a9e</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[binary-tree]]></category>
            <category><![CDATA[fb]]></category>
            <category><![CDATA[level-order-traversal]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[可愛小松鼠 Cute Squirrel]]></dc:creator>
            <pubDate>Mon, 18 Sep 2023 12:14:44 GMT</pubDate>
            <atom:updated>2023-09-18T12:14:44.864Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*GhNQ8iiKjNRpBzoJ.jpg" /><figcaption>BFS 先天具有 點播源擴散，逐層由內往外探索的特質</figcaption></figure><p>題目在這裡:</p><p><a href="https://leetcode.com/problems/binary-tree-level-order-traversal/description">LeetCode - The World&#39;s Leading Online Programming Learning Platform</a></p><p>題目會給定給我們一顆二元樹的根結點，要求我們輸出Level-order traversal的拜訪結果。</p><p>測試範例:</p><p><strong>Example 1:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/277/0*yTLKNxWWRPSgvVIq.jpg" /></figure><pre>Input: root = [3,9,20,null,null,15,7]<br>Output: [[3],[9,20],[15,7]]</pre><p><strong>Example 2:</strong></p><pre>Input: root = [1]<br>Output: [[1]]</pre><p><strong>Example 3:</strong></p><pre>Input: root = []<br>Output: []</pre><p>演算法:</p><p>其實這題就剛好可以套用圖論裡面的BFS廣度優先探索演算法，也呼應之前我們在<a href="https://medium.com/@cutesciuridae/%E5%9C%96%E8%AB%96graph-theory%E5%B8%B8%E7%94%A8%E7%9A%84%E5%B9%BE%E5%80%8B%E6%BC%94%E7%AE%97%E6%B3%95%E7%9A%84%E6%AF%94%E8%BC%83-216e85042133">圖論演算法統整</a>介紹過的概念。</p><p>BFS在探索Tree/Binary tree相關的領域中，還有一個名字，叫做<strong>Level-order traversal 逐層探索演算法</strong>。<strong>從第一層</strong>Root根接點，<strong>逐層探索</strong>到Leaf葉子節點 也是<strong>最深的那一層</strong>。</p><p>複習一下常見的BFS模板:</p><pre>traversalQ = [startNode]<br>visited = set()<br><br>while traversalQ:<br>  <br>  curNode = traversalQ.popleft()<br>  // do something, or print something<br>  visited.add( curNode )   <br><br>  for neighbor in graph[curNode]:<br>    if neighbor not in visited:<br>      traversalQ.append( neighbor )</pre><p>把BFS廣度優先演算法具象化，實作Binary tree的Level order traversal</p><pre>class Solution:<br>    def levelOrder(self, root: TreeNode) -&gt; List[List[int]]:<br>        <br>        <br>        if not root:<br>            # Quick response for empty tree<br>            return []<br>        <br>        traversalQ, result = deque([root]), []<br>        <br>        # level order traversal<br>        while traversalQ:<br>            <br>            # going down level-by-level<br>            cur_level_trace, cur_level_len = [], len(traversalQ)<br><br>            for _ in range(cur_level_len):<br>                <br>                cur_node = traversalQ.popleft()<br>                                    <br>                cur_level_trace.append(cur_node.val)<br>                cur_node.left and traversalQ.append( cur_node.left )<br>                cur_node.right and traversalQ.append( cur_node.right )<br>               <br>            <br>            result.append( cur_level_trace )<br>            <br>        return result</pre><p>時間複雜度:</p><p>O( n ) 每個節點最多拜訪一次。</p><p>空間複雜度:</p><p>O( n ) 最深的那一層在最後一層，最長為O( n/2 )</p><p>Reference:</p><p>[1] <a href="https://leetcode.com/problems/binary-tree-level-order-traversal/solutions/642012/python-js-java-go-c-o-n-by-bfs-w-comment/">Python/JS/Java/Go/C++ O(n) by BFS [w/ Comment ] — Binary Tree Level Order Traversal — LeetCode</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=102d900a9a9e" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[二元樹的拜訪 結合 DFS深度優先模板]]></title>
            <link>https://medium.com/@cutesciuridae/%E4%BA%8C%E5%85%83%E6%A8%B9%E7%9A%84%E6%8B%9C%E8%A8%AA-%E7%B5%90%E5%90%88-dfs%E6%B7%B1%E5%BA%A6%E5%84%AA%E5%85%88%E6%A8%A1%E6%9D%BF-750ad79fb832?source=rss-59c68f365a24------2</link>
            <guid isPermaLink="false">https://medium.com/p/750ad79fb832</guid>
            <category><![CDATA[binary-tree-traversal]]></category>
            <category><![CDATA[post-order]]></category>
            <category><![CDATA[pre-order]]></category>
            <category><![CDATA[in-order]]></category>
            <category><![CDATA[dfs]]></category>
            <dc:creator><![CDATA[可愛小松鼠 Cute Squirrel]]></dc:creator>
            <pubDate>Mon, 18 Sep 2023 05:12:10 GMT</pubDate>
            <atom:updated>2023-09-18T08:26:40.809Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*s-pCBsUMIuDvB3Jh.jpg" /></figure><p>其實常見的tree traversal，背後的<strong>核心觀念都是相同</strong>，</p><p><strong>Tree traversal其實就是探索整顆樹的搜索空間</strong>，也可以說是<strong>探索整顆樹</strong>，</p><p>只是<strong>指定順序略有不同</strong>而已。</p><p>再次回顧，經典的DFS模板</p><pre>def dfs( parameter ):<br>  <br>  if stop condition:<br>    # update final result if needed<br>    return result<br>  <br>  # general cases:<br>  dfs( updated parameter )<br>  return result</pre><p>應用到樹的搜索，preorder/ inorder/ postorder traversal 就變成</p><pre>def dfs( parameter ):<br>  <br>  if stop condition:<br>    # update final result if needed<br>    return []<br>  <br>  # general cases:<br><br><br>  # preorder: add current node to path<br><br>  dfs( left sub tree )<br><br>  # inorder: add current node to path<br><br>  dfs( right sub tree )<br><br>  # postorder: add current node to path<br><br>  return path</pre><p>其實三者背後的架構是共通的，只有次序稍微調整一下而已</p><p>具象化成<a href="https://leetcode.com/problems/binary-tree-preorder-traversal/description">preorder traversal</a>，就變成了這個樣子</p><p><a href="https://leetcode.com/problems/binary-tree-preorder-traversal/description">Binary Tree Preorder Traversal - LeetCode</a></p><pre>class Solution:<br>    def preorderTraversal(self, root: TreeNode) -&gt; List[int]:<br>        <br>        traversal_path = []<br>        <br>        def preorder( node ):<br>            <br>            if node:<br>            <br>                # DFS with preorder:<br>                # current, current.left, current.right   <br>                traversal_path.append( node.val )<br>                preorder( node.left )<br>                preorder( node.right )<br>        <br>        # -----------------------------------<br>        preorder(root)<br>        return traversal_path</pre><p>如果再用functional programming 的方式改寫，就變成</p><pre>class Solution:<br>    def preorderTraversal(self, root: Optional[TreeNode]) -&gt; List[int]:<br>        <br>        preOrder = lambda node: ( [node.val] + preOrder(node.left) + preOrder(node.right)  ) if node else [] <br>        <br>        return preOrder(root)</pre><p>再具象化成<a href="https://leetcode.com/problems/binary-tree-inorder-traversal/description/">inorder traversal</a>，就變成了這個樣子</p><p><a href="https://leetcode.com/problems/binary-tree-inorder-traversal/description">LeetCode - The World&#39;s Leading Online Programming Learning Platform</a></p><pre>class Solution:<br>    def inorderTraversal(self, root: Optional[TreeNode]) -&gt; List[int]:<br>        <br>        traversal_path = []<br>        <br>        def inorder( node ):<br>            <br>            if node:<br>            <br>                # DFS with inorder:<br>                # current.left, current, current.right   <br>                inorder( node.left )<br>                traversal_path.append( node.val )<br>                inorder( node.right )<br>        <br>        # -----------------------------------<br>        inorder(root)<br>        return traversal_path</pre><p>如果再用functional programming 的方式改寫，就變成</p><pre>class Solution:<br>    def inorderTraversal(self, root: Optional[TreeNode]) -&gt; List[int]:<br><br>        inOrder = lambda node: ( inOrder(node.left) + [node.val] + inOrder(node.right)  ) if node else [] <br><br>        return inOrder(root)</pre><p>同樣的手法，再具象化成<a href="https://leetcode.com/problems/binary-tree-postorder-traversal/description">postorder traversal</a>，就變成了這個樣子</p><p><a href="https://leetcode.com/problems/binary-tree-postorder-traversal/description">LeetCode - The World&#39;s Leading Online Programming Learning Platform</a></p><pre>class Solution:<br>    def postorderTraversal(self, root: Optional[TreeNode]) -&gt; List[int]:<br>        <br>        traversal_path = []<br>        <br>        def postorder( node ):<br>            <br>            if node:<br>            <br>                # DFS with postorder:<br>                # current.left, current.right, current<br>                postorder( node.left )<br>                postorder( node.right )<br>                traversal_path.append( node.val )<br>        <br>        # -----------------------------------<br>        postorder(root)<br>        return traversal_path</pre><p>如果再用functional programming 的方式改寫，就變成</p><pre>class Solution:<br>    def postorderTraversal(self, root: Optional[TreeNode]) -&gt; List[int]:<br>        <br>        postOrder = lambda node: ( postOrder(node.left) + postOrder(node.right) + [node.val]  ) if node else [] <br><br>        return postOrder(root)</pre><p>Reference:</p><p>[1] <a href="https://leetcode.com/problems/binary-tree-preorder-traversal/">https://leetcode.com/problems/binary-tree-preorder-traversal/</a></p><p>[2] <a href="https://leetcode.com/problems/binary-tree-inorder-traversal/">https://leetcode.com/problems/binary-tree-inorder-traversal/</a></p><p>[3] <a href="https://leetcode.com/problems/binary-tree-postorder-traversal/">https://leetcode.com/problems/binary-tree-postorder-traversal/</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=750ad79fb832" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>