數(shù)據(jù)結(jié)構(gòu)(Java)——Day15(二叉樹(shù)的OJ題目練習(xí)2)-創(chuàng)新互聯(lián)

1. 二叉樹(shù)的完全性校驗(yàn)：958. 二叉樹(shù)的完全性檢驗(yàn) - 力扣（Leetcode）

1. 思路

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

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

將一棵完全二叉樹(shù)看作兩個(gè)階段

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

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

遍歷完整個(gè)二叉樹(shù)，沒(méi)有返回false，則是一顆完全二叉樹(shù)

注意：當(dāng)a.中碰到只有右子樹(shù)沒(méi)有左子樹(shù)的節(jié)點(diǎn)直接return false即可

2. 實(shí)現(xiàn)代碼

2. 前序遍歷的非遞歸寫(xiě)法：144. 二叉樹(shù)的前序遍歷 - 力扣（Leetcode）

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

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

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

b. 當(dāng)棧不為空的時(shí)候進(jìn)行循環(huán)。出棧一個(gè)節(jié)點(diǎn)，則先將其右節(jié)點(diǎn)壓棧，再將其左節(jié)點(diǎn)壓棧，如果沒(méi)有，則不用壓棧

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

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

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

C. 注意(重中之重)：在Leetcode和?？椭袘?yīng)當(dāng)避免使用靜態(tài)變量和靜態(tài)方法，盡管語(yǔ)法上可能沒(méi)有錯(cuò)誤

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

例如：

用戶(hù)1：

Solution144 s1 = new Solution144();

用戶(hù)2：

Solution144 s2 = new Solution 144();

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

b. 示例：

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

3. 中序遍歷的非遞歸寫(xiě)法：94. 二叉樹(shù)的中序遍歷 - 力扣（Leetcode）

(1)思路：

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

4. 后序遍歷的非遞歸寫(xiě)法：145. 二叉樹(shù)的后序遍歷 - 力扣（Leetcode）

(1)思路：

A. 如何確定一個(gè)節(jié)點(diǎn)的右子樹(shù)不為空的時(shí)候是否是遍歷完畢

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

a. 首先向左下走到底

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

<1>判斷cur的右子樹(shù)是否處理過(guò)了：cur.right == null || cur.right = prev.

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

ret.add(cur.val);

//更新指針

prev = cur;

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

cur = null;

<2>若不滿(mǎn)足，則說(shuō)明cur.right != null && cur.right != prev(表示右子樹(shù)不為空且右子樹(shù)未被處理過(guò))

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

然后讓cur = cur.right，先處理右子樹(shù)

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

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

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

注意：明確什么時(shí)候打印空擴(kuò)號(hào)：當(dāng)左子樹(shù)為空，右子樹(shù)不為空的時(shí)候需要打印空擴(kuò)號(hào)，其他情況無(wú)需打印空擴(kuò)號(hào)

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

B. 終止條件：當(dāng)待處理的節(jié)點(diǎn)走到null的時(shí)候返回空字符串

C. 遞歸過(guò)程：

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

b. 處理左子樹(shù)：

<1>當(dāng)左子樹(shù)不為空的時(shí)候

append("(");

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

append(")");

<2>當(dāng)左子樹(shù)為空，右子樹(shù)不為空，則打印一個(gè)空擴(kuò)號(hào)

c. 處理右子樹(shù)：

當(dāng)右子樹(shù)不為空：

append("(");

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

append(")");

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

6. 二叉樹(shù)的最近公共祖先：

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

(1)思路：遞歸

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

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

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

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

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

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

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

廣告

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