打基礎之LeetCode算法題第48日:試試這道難倒實力大牛的題

打基礎之LeetCode算法題第48日:試試這道難倒實力大牛的題

一直很糾結算法的文章應該怎麼寫。最後覺得還是從最簡單的level開始寫吧,一開始就弄些重量級的,什麼人工智能,機器學習的算法,還要有大量的數學以及優化的知識,小白們估計會很鬱悶,當然我也不一定能做出來對吧。

我計劃每題給出兩種語言的解決方案,一種靜態語言,一種動態語言。

我選擇C語言,Python和Java作為實現語言,由於篇幅有限,其他語言的實現有興趣的朋友請自己嘗試。

LeetCode 226. 翻轉二叉樹(Invert Binary Tree)

問題描述:

翻轉一棵二叉樹。

注:

這個問題是受到 Max Howell 的 原問題 啟發的 :

打基礎之LeetCode算法題第48日:試試這道難倒實力大牛的題

谷歌:我們90%的工程師使用您編寫的軟件(Homebrew),但是您卻無法在面試時在白板上寫出翻轉二叉樹這道題,這太糟糕了。

示例:

打基礎之LeetCode算法題第48日:試試這道難倒實力大牛的題

很多人可能不知道Max Howell 是何須人也,但是如果你有一臺蘋果的MAC,那麼你一定用過Homebrew,它是OS X中的軟件包管理器,類似linux中的yum或apt。Max Howell 是Homebrew的作者,是實打實的大牛。關於他對google的諷刺可以看出來,程序員都是很高傲的,即使沒有通過筆試。

不過話說出來了,這個題目確實是簡單呀,通不過確實是有點不應該呀。雖然說大部分的基礎的算法問題,已經有現成的實現,基本不用再造車,但是算法問題和工程問題沒有本質區別,如果被問到了,你至少要給出一種可能的解決方案。

不過話說回來了,筆試做不出來,並不能證明你不是技術大牛。估計做技術的都有此遭遇,總覺得筆試過不,懷才不遇呀。

C語言實現:

翻轉就是互換左右節點。所以遞歸最適合做這個事情。

代碼如下:

打基礎之LeetCode算法題第48日:試試這道難倒實力大牛的題

注意不能直接賦值,因為你一旦直接賦值,接下來的再引用就是錯誤的了。

所以要用中間變量來傳遞。

打基礎之LeetCode算法題第48日:試試這道難倒實力大牛的題

python語言的實現:

python支持元祖賦值,所以不需要中間變量來傳遞值,所以代碼可以進一步精簡如下:

打基礎之LeetCode算法題第48日:試試這道難倒實力大牛的題

打基礎之LeetCode算法題第48日:試試這道難倒實力大牛的題

Java語言的實現:

Java的實現和C語言的實現一致,交換的時候也需要中間變量來傳遞。

打基礎之LeetCode算法題第48日:試試這道難倒實力大牛的題

打基礎之LeetCode算法題第48日:試試這道難倒實力大牛的題


分享到:


相關文章: