Selama wawancara, saya menemukan sebuah pertanyaan: Bagaimana menemukan simpul daun terjauh dari pohon biner, dan jarak dari simpul daun ini ke simpul akar?
Reaksi pertama jelas merupakan rekursi
Bagaimana kita dapat menemukan simpul daun terjauh dan juga merekam jarak dari simpul daun ini ke simpul akar? Gunakan daftar untuk mempertahankan jalur dari simpul akar ke simpul daun. Panjang daftar ini adalah -1, yang merupakan jarak dari simpul daun ke simpul akar. Node terakhir dari daftar ini adalah ke simpul daun.
Saya tidak perlu merancang pohon biner. Lihat artikel lain untuk kode tertentu.
/ *** Temukan simpul daun terjauh*/ public void findFarestleaf () {list <node> path = ArrayList baru <node> (); Daftar <Node> longestpath = findlongestpath (root, path); Node leaf = longestpath.get (longestpath.size () - 1); System.out.println ("simpul daun terjauh adalah <" + leaf.key + "," + leaf.value + ">, dan jarak ke simpul akar adalah:" + (longestpath.size () - 1)); } Daftar Publik <Node> findLongestPath (node x, daftar <node> path) {if (x == null) path return; // Setiap rekursi harus dibuat, jika tidak, cabang rekursif akan dilakukan pada daftar yang sama. Bahkan, semua node ditambahkan ke daftar ini. Daftar <Node> Currpath = ArrayList baru <Node> (); Currpath.addall (path); Currpath.add (x); Daftar <Node> leftpath = findlongestpath (x.left, Currpath); Daftar <Node> RightPath = FindLongestPath (X.Right, Currpath); if (leftpath.size ()> rightpath.size ()) mengembalikan leftpath; lain kembali RightPath; }Artikel di atas yang mencari simpul daun terjauh (penjelasan contoh) dari pohon biner adalah semua konten yang saya bagikan dengan Anda. Saya harap ini dapat memberi Anda referensi dan saya harap Anda dapat mendukung wulin.com lebih lanjut.