我開了一個LeetCode會員，選擇了一些高頻率題目。這個系列是希望幫助大家每天花30分鐘的題目了解面試高頻題，讓大家面試更加游刃有余。

本期我們講解兩道樹的中等題。我們之前幾期的推送一直在強調遞歸和迭代，之前講解的題目遞歸都比迭代簡單，那么本期首先帶來的就是迭代比遞歸更容易的題目。本期所用的樹的數據結構均如下：

class

114. 二叉樹展開為鏈表

題意：給定一棵樹，根據前序遍歷將其展開為一個【只有右子樹有值的，左子樹為null的】類似于鏈表的結構，如下圖

拿上圖給出的例題作分析，我們發現4這個結點的右子樹結點應該是5，但是怎么去找到5呢？是不是要把5先存起來，然后4才能找到5。那我們第一反應就是用一個數據結構去存儲結點。那這就是迭代的思路，數據結構就先從隊列和棧考慮，一般來講，廣搜用隊列，深搜用棧，這里的前序遍歷顯然是深搜，那么我們用棧。因為前序遍歷的順序是根節點->左->右，所以我們先把右子樹結點入棧，再把左子樹結點入棧，然后依次操作。

迭代比遞歸好的一點，就是能根據代碼很好的演算，如果大家還沒有搞懂上面的思路，就根據下面的代碼演算一遍吧。

public

那么這可以用遞歸做嗎？答案是肯定的，遞歸的好處是代碼簡練、可讀性高，但是比較難想、比較難演算，完整代碼如下：

private

看上去是不是很簡單，只要幾行就搞定了。我一直覺得遞歸的邏輯很難想，除非是那種一眼就知道的。那其實一眼就知道的題目也是歸功于自己練習的多，所以想完全熟悉遞歸的題目，那就多做吧！上面的代碼其實是先找了最右邊的一個結點，然后反向往前操作。

我們做了那么多關于樹的遞歸題目，其實無非就是兩點：1.先遞歸左子樹還是先遞歸右子樹；2.邏輯放在遞歸前還是邏輯放在遞歸后。我們之后會出一個總結專題來好好講講樹的遞歸。

95. 最大二叉樹

題意： 給定一個不含重復元素的整數數組。一個以此數組構建的最大二叉樹定義如下： 1.二叉樹的根是數組中的最大元素。 2.左子樹是通過數組中最大值左邊部分構造出的最大二叉樹。 3.右子樹是通過數組中最大值右邊部分構造出的最大二叉樹。 4.通過給定的數組構建最大二叉樹，并且輸出這個樹的根節點。

這道題其實是一道簡單版的構造一棵“二叉搜索樹”，只是這的“二叉搜索樹”被題中規定的“最大樹”替換了。這道題的遞歸方法是比較簡單的，代碼如下：

public

這道題有難度的是迭代方法，我們說迭代方法一定是要有定義一個用于存儲結點的數據結構的，那么這道題的數據結構應該是什么？從棧和隊列里考慮，這道題是深搜，應該是棧。但我們嘗試用棧做下去之后發現，需要用到一個特殊的棧——雙向隊列，這是一種具有隊列和棧的性質的數據結構。迭代的另一個難點是入棧（隊列）和出棧（隊列）的順序和時機，我們來看代碼：

public

注意這道題用雙向隊列的唯一原因就是最后一個return，主要邏輯和棧一樣，所以我們說這道題的思路是先選擇棧，最后再替換成雙向隊列。

關注公眾號，更多算法知識點告訴你。

總結

以上是生活随笔為你收集整理的找二叉树中给定元素的的左孩子结点_LeetCode高频题：二叉树（五）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。