Menyongsangkan pokok binari di Jawa

Baru-baru ini, saya mula berlatih beberapa latihan LeetCode untuk meningkatkan kemahiran algoritma/struktur data saya. Saya boleh katakan bahawa platform ini menyediakan persekitaran yang baik untuk berlatih dan belajar dengan penyelesaian pembangun lain dalam beberapa bahasa pengaturcaraan, berbincang, berkongsi penyelesaian dengan orang lain dan mengamalkan cabaran kod yang diminta oleh syarikat besar.

Apakah LeetCode?

LeetCode ialah tapak web yang membantu calon membuat persediaan untuk temuduga pengekodan. Pengguna boleh mempraktikkan cabaran dengan menggunakan pengekodan platform dan masalah algoritma, bersama-sama dengan ujian pratakrif untuk penyelesaian calon. LeetCode telah menjadi sumber popular untuk wawancara teknikal dan pertandingan pengekodan, bersama-sama dengan HackerRank.

Rutin saya menyelesaikan masalah

Saya meletakkan diri saya pada matlamat untuk menyelesaikan sekurang-kurangnya 3 cabaran setiap hari, dan cara saya berfikir dalam penyelesaian melibatkan iPad saya, pen untuk skrin dan apl Freeform. Saya cuba melukis dan memikirkan penyelesaiannya, dan ini banyak membantu dalam penyerahan kod saya. Banyak cabaran kedengaran sukar pada pandangan pertama, tetapi dengan beberapa minit berfikir dan mereka bentuk penyelesaiannya (saya cadangkan menulis proses pemikiran anda). Jika saya tidak dapat mencari penyelesaian yang betul dalam masa 30 minit, maka saya melihat penyerahan daripada pembangun lain untuk mengetahui di mana kesilapan saya (kadang-kadang langkah kecil yang saya terlupa dalam kod saya). Walaupun penyelesaian anda cukup baik, saya sangat mengesyorkan melihat penyerahan orang lain untuk memikirkan cara lain untuk menyelesaikan masalah itu (sesetengahnya lebih atau kurang cekap).

Masalah Pokok Binari Songsang

Beberapa hari yang lalu saya menghadapi masalah Invert Binary Tree di LeetCode, cabaran terkenal yang diminta dalam beberapa temu bual dan masalah yang saya lihat semasa mengikuti kelas Struktur Data/Algoritma di universiti. Walaupun saya tidak pernah menghadapi cabaran ini dalam temu duga dan tidak pernah secara eksplisit menyongsangkan pokok binari dalam kerja saya, mengetahui cara menyongsangkan satu memberi saya lebih banyak pengalaman dengan pemikiran DS, Pokok dan algoritma serta mempraktikkan beberapa teknik seperti rekursi.
Saya mengesyorkan anda cuba menyelesaikan masalah ini sebelum membaca artikel ini yang lain

Penyelesaiannya

Masalah Pokok Binari Terbalik meminta saya "Memberi akar pokok binari, terbalikkan pokok itu, dan kembalikan akarnya." (dalam erti kata lain, kita harus "mencerminkan" pokok itu). Saya menggunakan bahasa pengaturcaraan Java untuk menyerahkan penyelesaian, tetapi langkahnya adalah sama untuk bahasa lain (dengan perubahan sintaks kecil). Contoh input dan output dijangka ditunjukkan di bawah:

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

Kami akan menggunakan teknik rekursi untuk memanggil kaedah invertTree() secara rekursif, melepasi beberapa bahagian pokok sebagai akar. Jadi, seperti yang diminta oleh setiap rekursi, kita perlu menentukan keadaan berhenti di mana tindanan rekursi akan selesai dan mengembalikan hasil masing-masing panggilan rekursi. Selepas itu, kami hanya menyongsangkan sisi pokok, menetapkan kepada root.left nilai yang dikembalikan oleh rekursi yang melepasi root.right sebagai parameter, dan melakukan perkara yang sama ke root.right memberikan nilai hasil rekursi root.left. Ketika kami mengubah suai nilai asal, kami memerlukan pembolehubah tambahan untuk menyimpan hasil asal root.left (anda mungkin melaksanakan kod seperti ini di universiti dan memanggilnya kaedah swap().

Pada akhirnya kami mengembalikan akar dengan nod terbalik. Anda boleh menyemak kod di bawah:

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

Perlu diingat bahawa terdapat banyak penyelesaian yang berbeza untuk masalah yang berbeza, dan itu bagus. Setiap orang mempunyai cara berfikir dan atur cara, domain Struktur Data dan lain-lain. Anda tidak perlu mengikuti kod yang sama untuk menyelesaikan masalah ini, tetapi anda mesti memberi perhatian kepada kerumitan algoritma (anda boleh menggunakan 3 bersarang untuk menyelesaikan masalah , tetapi ini kurang berprestasi berbanding menggunakan 1 untuk).

Atas ialah kandungan terperinci Menyongsangkan pokok binari di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!