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

資訊專欄INFORMATION COLUMN

[Leetcode] Invert Binary Tree 翻轉(zhuǎn)二叉樹

leone / 1008人閱讀

摘要：原題鏈接遞歸法復(fù)雜度時間空間遞歸棧空間思路這個難倒大神的題也是非常經(jīng)典的一道測試對二叉樹遍歷理解的題。遞歸的終止條件是當(dāng)遇到空節(jié)點或葉子節(jié)點時，不再交換，直接返回該節(jié)點。代碼給出的是后序遍歷的自下而上的交換，先序遍歷的話就是自上而下的交換。

Invert Binary Tree 
Invert a binary tree.


     4
   /   
  2     7
 /    / 
1   3 6   9



to


     4
   /   
  7     2
 /    / 
9   6 3   1



Trivia: This problem was inspired by this original tweet by Max
Howell:


Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

原題鏈接

遞歸法 復(fù)雜度

時間 O(N) 空間 O(N) 遞歸?？臻g

思路

這個難倒Max Howell大神的題也是非常經(jīng)典的一道測試對二叉樹遍歷理解的題。遞歸的終止條件是當(dāng)遇到空節(jié)點或葉子節(jié)點時，不再交換，直接返回該節(jié)點。對于其他的節(jié)點，我們分別交換它的左子樹和右子樹，然后將交換過后的左子樹賦給右節(jié)點，右子樹賦給左節(jié)點。代碼給出的是后序遍歷的自下而上的交換，先序遍歷的話就是自上而下的交換。

代碼 
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) return root;
        TreeNode newLeft = invertTree(root.right);
        TreeNode newRight = invertTree(root.left);
        root.left = newLeft;
        root.right = newRight;
        return root;
    }
}
迭代法 復(fù)雜度

時間 O(N) 空間 O(1)

思路

迭代法的思路是BFS或者DFS，這兩種方法都可以實現(xiàn)，實際上也是二叉樹的遍歷。BFS用Queue實現(xiàn)，DFS的話將代碼中的Queue換成Stack。

代碼 
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        Queue q = new LinkedList();
        if(root!=null) q.offer(root);
        while(!q.isEmpty()){
            TreeNode curr = q.poll();
            TreeNode tmp = curr.right;
            curr.right = curr.left;
            curr.left = tmp;
            if(curr.left!=null) q.offer(curr.left);
            if(curr.right!=null) q.offer(curr.right);
        }
        return root;
    }
}

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

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

相關(guān)文章

  • LeetCode 之 JavaScript 解答第226題 —— 翻轉(zhuǎn)二叉樹（Invert Bina

    摘要：算法思路判斷樹是否為空同時也是終止條件。分別對左右子樹進行遞歸。代碼實現(xiàn)判斷當(dāng)前樹是否為左右子樹結(jié)點交換分別對左右子樹進行遞歸返回樹的根節(jié)點歡迎一起加入到開源倉庫，可以向提交您其他語言的代碼。 Time：2019/4/21Title: Invert Binary TreeDifficulty: EasyAuthor: 小鹿 題目：Invert Binary Tree（反轉(zhuǎn)二叉樹） ...

    MingjunYang 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

    摘要：微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...

    warmcheng 評論0 收藏0

  • 前端 | 每天一個 LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

    張漢慶 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...

    tain335 評論0 收藏0

  • LeetCode 156 Binary Tree Upside Down 上下翻轉(zhuǎn)二叉樹

    摘要：翻轉(zhuǎn)以后如下解題思路翻轉(zhuǎn)的形式一開始不是很清楚，但是里面的高票答案給了一個很好的解釋?？蠢樱瑯涞淖筮呑钌畹牡讓邮?，是新的。對于每個，將鏈接右孩子的指針去掉，將變?yōu)楫?dāng)前左孩子的，成為左孩子的。遞歸的寫法遞歸調(diào)用得到新的，并且沿途改變結(jié)構(gòu)。 LeetCode 156 Binary Tree Upside Down Given a binary tree where all the rig...

    Loong_T 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<