成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

力扣

Carbs / 2818人閱讀

摘要：題目題目劍指二叉樹的鏡像思路遞歸思路遞歸我們可以使用深度優(yōu)先搜索，先遞歸到鏈表的末尾，然后從末尾開始兩兩交換。

題目

劍指 Offer 27. 二叉樹的鏡像

思路1（遞歸）

  • 我們可以使用深度優(yōu)先搜索，先遞歸到鏈表的末尾，然后從末尾開始兩兩交換。就相當(dāng)于后續(xù)遍歷而已
  • 記得要先保存下來(lái)node.right節(jié)點(diǎn)，因?yàn)槲覀冊(cè)谶f歸完左邊才遞歸右邊，而遞歸完左邊的時(shí)候，直接把node.right的指向修改了，如果事先不保存node.right節(jié)點(diǎn)的話，在遞歸右邊傳入的節(jié)點(diǎn)是錯(cuò)誤的節(jié)點(diǎn)，因此得不到正確的答案

代碼

class Solution {    public TreeNode mirrorTree(TreeNode root) {        return dfs(root);    }    public TreeNode dfs(TreeNode node) {        // 為空說(shuō)明到底了        if (node == null) {            return null;        }        // 先記錄right節(jié)點(diǎn)        TreeNode right = node.right;        // 分別遞歸左邊和右邊，將 left 和 right 的指針互相交換        node.right = mirrorTree(node.left);        node.left = mirrorTree(right);        return node;    }}

復(fù)雜度分析

  • 時(shí)間復(fù)雜度：/(O(N)/)，遍歷一遍樹的每個(gè)節(jié)點(diǎn)要花費(fèi)/(O(N)/)的時(shí)間復(fù)雜度
  • 空間復(fù)雜度：/(O(N)/)，最壞情況下是一條鏈表，因此遞歸需要/(O(N)/)的?？臻g

思路2（迭代）

  • 使用隊(duì)列（也可以使用棧，差不多一樣）進(jìn)行存儲(chǔ)節(jié)點(diǎn)，就是數(shù)的層序遍歷
  • 節(jié)點(diǎn)是按順序入隊(duì)，因此我們需要做的就是將隊(duì)頭元素出隊(duì)，然后將他的兩個(gè)子節(jié)點(diǎn)入隊(duì)，再交換兩個(gè)子節(jié)點(diǎn)的值就可以完成一個(gè)子節(jié)點(diǎn)左右孩子的交換，重復(fù)所有的節(jié)點(diǎn)
  • 其實(shí)就是從樹根到樹葉將每個(gè)子節(jié)點(diǎn)都進(jìn)行交換，最終完成了整個(gè)樹的交換，形成鏡像

代碼

class Solution {    public TreeNode mirrorTree(TreeNode root) {        if (root == null) {            return null;        }        // 使用隊(duì)列存儲(chǔ)節(jié)點(diǎn)        Queue queue = new LinkedList<>();        queue.offer(root);        while (!queue.isEmpty()) {            TreeNode node = queue.poll();            // 將子節(jié)點(diǎn)入隊(duì)            if (node.left != null) {                queue.offer(node.left);            }            if (node.right != null) {                queue.offer(node.right);            }            // 交換左右兩個(gè)子節(jié)點(diǎn)            TreeNode temp = node.left;            node.left = node.right;            node.right = temp;        }        return root;    }}

復(fù)雜度分析

  • 時(shí)間復(fù)雜度：/(O(N)/)
  • 空間復(fù)雜度：/(O(N)/)，棧最多存儲(chǔ) /(/frac{N + 1}{2}/)個(gè)節(jié)點(diǎn)
我走得很慢，但我從不后退！

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/124813.html

相關(guān)文章

  • 思維導(dǎo)圖整理大廠面試高頻數(shù)組補(bǔ)充1: 最接近的三數(shù)之和 和 三數(shù)之和 的兩個(gè)不同之處, 力扣16

    摘要：此專欄文章是對(duì)力扣上算法題目各種方法的總結(jié)和歸納整理出最重要的思路和知識(shí)重點(diǎn)并以思維導(dǎo)圖形式呈現(xiàn)當(dāng)然也會(huì)加上我對(duì)導(dǎo)圖的詳解目的是為了更方便快捷的記憶和回憶算法重點(diǎn)不用每次都重復(fù)看題解畢竟算法不是做了一遍就能完全記住的所 ...

    longmon 評(píng)論0 收藏0

  • 力扣(LeetCode)310

    摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個(gè)圖，寫出一個(gè)函數(shù)找到所有的最小高度樹并返回他們的根節(jié)點(diǎn)。因此使用一個(gè)數(shù)組代表每個(gè)節(jié)點(diǎn)的入度，若入度為就是葉子節(jié)點(diǎn)。 題目地址：https://leetcode-cn.com/probl...題目描述： 對(duì)于一個(gè)具有樹特征的無(wú)向圖，我們可選擇任何一個(gè)節(jié)點(diǎn)作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...

    amuqiao 評(píng)論0 收藏0

  • ??思維導(dǎo)圖整理大廠面試高頻數(shù)組9: 刪除重復(fù)元素的通解問(wèn)題, 力扣26/80??

    此專欄文章是對(duì)力扣上算法題目各種方法的總結(jié)和歸納, 整理出最重要的思路和知識(shí)重點(diǎn)并以思維導(dǎo)圖形式呈現(xiàn), 當(dāng)然也會(huì)加上我對(duì)導(dǎo)圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(diǎn)(不用每次都重復(fù)看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經(jīng)知道解題思路和方法, 想進(jìn)一步加強(qiáng)理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據(jù)題號(hào)先去力扣看看官方題解, 然后再看本文內(nèi)容). 關(guān)...

    MasonEast 評(píng)論0 收藏0

  • ??思維導(dǎo)圖整理大廠面試高頻數(shù)組19: 股票問(wèn)題III的dp數(shù)組構(gòu)建/初始化和空間優(yōu)化難點(diǎn), 力扣1

    此專欄文章是對(duì)力扣上算法題目各種方法的總結(jié)和歸納, 整理出最重要的思路和知識(shí)重點(diǎn)并以思維導(dǎo)圖形式呈現(xiàn), 當(dāng)然也會(huì)加上我對(duì)導(dǎo)圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(diǎn)(不用每次都重復(fù)看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經(jīng)知道解題思路和方法, 想進(jìn)一步加強(qiáng)理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據(jù)題號(hào)先去力扣看看官方題解, 然后再看本文內(nèi)容). 關(guān)...

    劉福 評(píng)論0 收藏0

  • ??導(dǎo)圖整理大廠面試高頻數(shù)組8: 移除元素的雙指針優(yōu)化, 力扣27??

    此專欄文章是對(duì)力扣上算法題目各種方法的總結(jié)和歸納, 整理出最重要的思路和知識(shí)重點(diǎn)并以思維導(dǎo)圖形式呈現(xiàn), 當(dāng)然也會(huì)加上我對(duì)導(dǎo)圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(diǎn)(不用每次都重復(fù)看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經(jīng)知道解題思路和方法, 想進(jìn)一步加強(qiáng)理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據(jù)題號(hào)先去力扣看看官方題解, 然后再看本文內(nèi)容). 關(guān)...

    zhangyucha0 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<