力扣

Carbs 發布于2021-11-24 09:39 / 2803人閱讀

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

題目

思路1（遞歸）

我們可以使用深度優先搜索，先遞歸到鏈表的末尾，然后從末尾開始兩兩交換。就相當于后續遍歷而已
記得要先保存下來node.right節點，因為我們在遞歸完左邊才遞歸右邊，而遞歸完左邊的時候，直接把node.right的指向修改了，如果事先不保存node.right節點的話，在遞歸右邊傳入的節點是錯誤的節點，因此得不到正確的答案

代碼

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

復雜度分析

時間復雜度：/(O(N)/)，遍歷一遍樹的每個節點要花費/(O(N)/)的時間復雜度
空間復雜度：/(O(N)/)，最壞情況下是一條鏈表，因此遞歸需要/(O(N)/)的棧空間

思路2（迭代）

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

代碼

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

復雜度分析

時間復雜度：/(O(N)/)
空間復雜度：/(O(N)/)，棧最多存儲 /(/frac{N + 1}{2}/)個節點

我走得很慢，但我從不后退！

云服務器 GPU云服務器力扣

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/124813.html

思維導圖整理大廠面試高頻數組補充1: 最接近的三數之和和三數之和的兩個不同之處, 力扣16

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

longmon 2021-11-12 10:36 評論0 收藏0
力扣(LeetCode)310

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

amuqiao 2019-08-16 16:13 評論0 收藏0
??思維導圖整理大廠面試高頻數組9: 刪除重復元素的通解問題, 力扣26/80??

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

MasonEast 2021-09-04 16:40 評論0 收藏0
??思維導圖整理大廠面試高頻數組19: 股票問題III的dp數組構建/初始化和空間優化難點, 力扣1

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

劉福 2021-10-11 10:59 評論0 收藏0
??導圖整理大廠面試高頻數組8: 移除元素的雙指針優化, 力扣27??

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

zhangyucha0 2021-09-02 15:11 評論0 收藏0