[Leetcode] Invert Binary Tree 翻轉二叉樹

leone 發布于2019-08-14 16:11 / 1000人閱讀

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

Invert Binary Tree

Invert a binary tree.

     4
   /   
  2     7
 /    / 
1   3 6   9

     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.

原題鏈接

遞歸法 復雜度

時間 O(N) 空間 O(N) 遞歸棧空間

思路

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

代碼

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;
    }
}

迭代法 復雜度

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

思路

迭代法的思路是BFS或者DFS，這兩種方法都可以實現，實際上也是二叉樹的遍歷。BFS用Queue實現，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;
    }
}

云服務器 GPU云服務器 binary-tree binary-search-tree 二叉樹 python二叉樹

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

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

LeetCode 之 JavaScript 解答第226題 —— 翻轉二叉樹（Invert Bina

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

MingjunYang 2019-08-23 17:07 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

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

warmcheng 2019-08-26 10:09 評論0 收藏0
前端 | 每天一個 LeetCode

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

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

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

tain335 2019-08-26 10:28 評論0 收藏0
LeetCode 156 Binary Tree Upside Down 上下翻轉二叉樹

摘要：翻轉以后如下解題思路翻轉的形式一開始不是很清楚，但是里面的高票答案給了一個很好的解釋?？蠢?，樹的左邊最深的底層是，是新的。對于每個，將鏈接右孩子的指針去掉，將變為當前左孩子的，成為左孩子的。遞歸的寫法遞歸調用得到新的，并且沿途改變結構。 LeetCode 156 Binary Tree Upside Down Given a binary tree where all the rig...

Loong_T 2019-08-16 13:28 評論0 收藏0