Java 中的倒置二元樹

最近，我開始練習一些 LeetCode 練習，以提高我的演算法/資料結構技能。我可以說，該平台提供了一個良好的環境，可以與其他開發人員一起練習和學習多種程式語言的解決方案，與他人討論、分享解決方案，並練習大公司要求的程式碼挑戰。

什麼是 LeetCode？

LeetCode 是一個幫助候選人準備程式設計面試的網站。使用者可以透過使用平台的編碼和演算法問題以及針對候選人解決方案的預定義測試來練習挑戰。 LeetCode 與 HackerRank 一樣，已成為技術面試和程式設計競賽的熱門資源。

我的日常解決問題

我給自己設定的目標是每天至少解決 3 個挑戰，我的解決方案思維方式涉及我的 iPad、一支螢幕筆和 Freeform 應用程式。我嘗試畫出並思考解決方案，這對我提交程式碼有很大幫助。許多挑戰乍看之下似乎很難，但只要花幾分鐘思考和建立解決方案（我建議寫下您的思考過程）。如果我在 30 分鐘內找不到正確的解決方案，那麼我會查看其他開發人員的提交來發現我的錯誤在哪裡（有時是我在程式碼中忘記的一小步）。即使您的解決方案足夠好，我也強烈建議您查看其他人提交的內容，以思考解決該問題的其他方法（或多或少有效）。

反轉二元樹問題

幾天前，我在 LeetCode 上遇到了反向二元樹問題，這是一些面試中要求的眾所周知的挑戰，也是我在大學上資料結構/演算法課程時看到的問題。雖然我從未在面試中遇到過這項挑戰，也從未在工作中明確地反轉二元樹，但知道如何反轉二元樹讓我在DS、樹和演算法思維方面獲得了更多經驗，並練習了一些諸如遞歸之類的技術。
我建議您在閱讀本文的其餘部分之前先嘗試解決這個問題

解決方案

反轉二元樹問題 要求我「給定二元樹的根，反轉樹，並返回其根。」（換句話說，我們應該「鏡像」樹）。我使用Java程式語言提交了一個解決方案，但其他語言的步驟是相同的（有小的語法變化）。輸入範例和預期輸出如下圖所示：

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

我們將使用遞歸技術遞歸呼叫 invertTree() 方法，並將樹的某一側作為根傳遞。因此，正如每個遞歸要求的那樣，我們需要定義一個停止條件，遞歸堆疊將在該條件下完成並傳回遞歸呼叫的相應結果。之後，我們只需反轉樹的邊，將root.right 作為參數傳遞給root.left 的遞歸返回值分配給root.left，並對root.right 執行相同的操作，將root.left 遞歸結果的值分配給root.right。 當我們修改原始值時，我們需要一個輔助變數來儲存root.left的原始結果（你可能在大學裡實現過這樣的程式碼，並稱之為swap()方法。

最後我們回到節點反轉的根。您可以檢查以下程式碼：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }

        TreeNode aux = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(aux);

        return root;
    }
}

請記住，對於不同的問題可能存在許多不同的解決方案，這很好。每個人都有自己的思維方式和程式設計方式，資料結構領域等。你不需要遵循完全相同的程式碼來解決這個問題，但你必須注意演算法複雜度（你可以使用3個嵌套的for來解決問題，但這比使用 1 的效能要差)。

以上是Java 中的倒置二元樹的詳細內容。更多資訊請關注PHP中文網其他相關文章！