1. 二叉樹的完全性校驗：958. 二叉樹的完全性檢驗 - 力扣（Leetcode）

1. 思路

成都創(chuàng)新互聯(lián)公司專注于長子企業(yè)網(wǎng)站建設(shè),成都響應(yīng)式網(wǎng)站建設(shè),商城網(wǎng)站開發(fā)。長子網(wǎng)站建設(shè)公司,為長子等地區(qū)提供建站服務(wù)。全流程定制網(wǎng)站開發(fā)，專業(yè)設(shè)計，全程項目跟蹤，成都創(chuàng)新互聯(lián)公司專業(yè)和態(tài)度為您提供的服務(wù)

(1)如何判斷一棵樹是否是完全二叉樹：分階段 + 層序遍歷

將一棵完全二叉樹看作兩個階段

a. 階段1：此時的階段都是度為2的節(jié)點，從左到右，從上到下遍歷，當碰到第一個只有左子樹沒有右子樹(度為1的節(jié)點)或者葉子節(jié)點時轉(zhuǎn)換階段，從該節(jié)點之后的節(jié)點都應(yīng)該處在階段2

b. 階段2：此時的節(jié)點全都是葉子節(jié)點，碰到一個反列，直接return false

遍歷完整個二叉樹，沒有返回false，則是一顆完全二叉樹

注意：當a.中碰到只有右子樹沒有左子樹的節(jié)點直接return false即可

2. 實現(xiàn)代碼

2. 前序遍歷的非遞歸寫法：144. 二叉樹的前序遍歷 - 力扣（Leetcode）

(1)思路：深度優(yōu)先遍歷：借助棧這個結(jié)構(gòu)進行遍歷。

A. 前序優(yōu)先遍歷的非遞歸：根左右

a. 首先將根節(jié)點壓入棧中

b. 當棧不為空的時候進行循環(huán)。出棧一個節(jié)點，則先將其右節(jié)點壓棧，再將其左節(jié)點壓棧，如果沒有，則不用壓棧

注意：為了保證出棧順序是根左右的順序，因此壓棧的時候是右節(jié)點先壓棧，左節(jié)點后壓棧?

B. 注意：一個題外話，樹的三種深度優(yōu)先遍歷的遞歸寫法的返回值數(shù)組ret應(yīng)該放在遞歸函數(shù)外

不然每次遞歸調(diào)用都會產(chǎn)生一個新的數(shù)組ret，每個ret只能保存當前節(jié)點的節(jié)點值，最終返回的是最外層的ret，導(dǎo)致結(jié)果集出錯

C. 注意(重中之重)：在Leetcode和牛客中應(yīng)當避免使用靜態(tài)變量和靜態(tài)方法，盡管語法上可能沒有錯誤

a. 原因：每個用戶提交的時候，LeetCode后臺會給不同的用戶創(chuàng)建該類的對象，使用不同的對象調(diào)來調(diào)用方法來跑測試用例，如果使用靜態(tài)變量或方法，就會造成其他用戶污染數(shù)據(jù)，造成自己測試用例報錯

例如：

用戶1：

Solution144 s1 = new Solution144();

用戶2：

Solution144 s2 = new Solution 144();

假設(shè)用戶2使用靜態(tài)變量來保存最終的結(jié)果集，則這個結(jié)果集其他用戶能夠修改，可能將其他用戶的結(jié)果值錯誤的拿過來導(dǎo)致報錯

b. 示例：

(2)代碼實現(xiàn)

3. 中序遍歷的非遞歸寫法：94. 二叉樹的中序遍歷 - 力扣（Leetcode）

(1)思路：

(2)代碼實現(xiàn)：

4. 后序遍歷的非遞歸寫法：145. 二叉樹的后序遍歷 - 力扣（Leetcode）

(1)思路：

A. 如何確定一個節(jié)點的右子樹不為空的時候是否是遍歷完畢

B. 循環(huán)過程思路：

a. 首先向左下走到底

b. 然后cur = stack.pop();

<1>判斷cur的右子樹是否處理過了：cur.right == null || cur.right = prev.

處理過，則說明cur可以出棧了，出棧后添加到結(jié)果集中

ret.add(cur.val);

//更新指針

prev = cur;

//注意：要將cur置為null，保證下一次循環(huán)cur指向新的棧頂，而不是死循環(huán)的壓棧出棧

cur = null;

<2>若不滿足，則說明cur.right != null && cur.right != prev(表示右子樹不為空且右子樹未被處理過)

因此將cur重新壓入棧中，stack.push(cur);

然后讓cur = cur.right，先處理右子樹

(2)代碼實現(xiàn)

5.?根據(jù)二叉樹創(chuàng)建字符串：606. 根據(jù)二叉樹創(chuàng)建字符串 - 力扣（Leetcode）

(1)思路：遞歸 + 前序遍歷

注意：明確什么時候打印空擴號：當左子樹為空，右子樹不為空的時候需要打印空擴號，其他情況無需打印空擴號

A. 函數(shù)語義：給定一個二叉樹的根節(jié)點，就能采用前序遍歷，將樹的所有節(jié)點轉(zhuǎn)換為規(guī)定的字符串并添加到結(jié)果集ret中

B. 終止條件：當待處理的節(jié)點走到null的時候返回空字符串

C. 遞歸過程：

a. 處理根：ret.append(root)

b. 處理左子樹：

<1>當左子樹不為空的時候

append("(");

遞歸調(diào)用：將root的左子樹的所有節(jié)點轉(zhuǎn)換為規(guī)定的字符串并添加到結(jié)果集中

append(")");

<2>當左子樹為空，右子樹不為空，則打印一個空擴號

c. 處理右子樹：

當右子樹不為空：

append("(");

遞歸調(diào)用：將root的右子樹的所有節(jié)點轉(zhuǎn)換為規(guī)定的字符串并添加到結(jié)果集中

append(")");

(2)代碼實現(xiàn)：

6. 二叉樹的最近公共祖先：

236. 二叉樹的最近公共祖先 - 力扣（Leetcode）

(1)思路：遞歸

A. 最近公共祖先：根據(jù)題目分析可知，某一個節(jié)點x，左子樹，右子樹三個位置上有兩個位置存在p和q，則x是p和q的最近公共祖先。即為下面的描述

B. 一個隱含的點：p和q的位置是固定的，因此不存在p同時出現(xiàn)在兩個位置甚至是三個位置，q也是同理。因此實際上這個left + right + mid的值不可能為3，因為p和q這兩個節(jié)點最多只能占據(jù)兩個位置

C. left + right + mid的情況：下列 等于1的情況應(yīng)該是有且只找到一個節(jié)點的情況

(2)代碼實現(xiàn)

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁題目：數(shù)據(jù)結(jié)構(gòu)(Java)——Day15(二叉樹的OJ題目練習2)-創(chuàng)新互聯(lián)
文章分享：http://www.chinadenli.net/article46/dhichg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、Google、企業(yè)建站、品牌網(wǎng)站建設(shè)、網(wǎng)站排名、用戶體驗

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)