ค้นหาโหนดใบไม้ที่ไกลที่สุดของต้นไม้ไบนารี (ตัวอย่างคำอธิบาย)

ในระหว่างการสัมภาษณ์ฉันพบคำถาม: วิธีการค้นหาโหนดใบไม้ที่ไกลที่สุดของต้นไม้ไบนารีและระยะทางจากโหนดใบนี้ไปยังโหนดรูท?

ปฏิกิริยาแรกคือการเรียกซ้ำอย่างแน่นอน

เราจะหาโหนดใบที่ไกลที่สุดและบันทึกระยะทางจากโหนดใบนี้ไปยังโหนดรูทได้อย่างไร ใช้รายการเพื่อรักษาเส้นทางจากโหนดรูทไปยังโหนดใบไม้ ความยาวของรายการนี้คือ -1 ซึ่งเป็นระยะทางจากโหนดใบไม้ไปยังโหนดรูท โหนดสุดท้ายของรายการคือโหนดใบไม้

ฉันไม่จำเป็นต้องออกแบบต้นไม้ไบนารี ดู บทความอื่น สำหรับรหัสเฉพาะ

 / *** ค้นหาโหนดใบไม้ที่ไกลที่สุด*/ โมฆะสาธารณะ findfarestleaf () {รายการ <node> path = new ArrayList <Node> (); รายการ <node> longestPath = findlongestPath (รูท, เส้นทาง); Node leaf = longestPath.get (longestPath.size () - 1); System.out.println ("โหนดใบที่ไกลที่สุดคือ <" + leaf.key + "," + leaf.value + "> และระยะทางไปยังโหนดรูทคือ:" + (longestpath.size () - 1)); } รายการสาธารณะ <Node> FindLongestPath (โหนด X, รายการ <node> เส้นทาง) {ถ้า (x == null) เส้นทางส่งคืน; // การเรียกซ้ำทุกครั้งจะต้องสร้างขึ้นมิฉะนั้นสาขาเรียกซ้ำจะทำในรายการเดียวกัน อันที่จริงโหนดทั้งหมดจะถูกเพิ่มลงในรายการนี้ รายการ <node> currpath = new ArrayList <Node> (); currpath.addall (เส้นทาง); currpath.add (x); รายการ <node> leftPath = findLongestPath (x.left, currpath); รายการ <node> rightPath = findlongestPath (x.right, currpath); if (leftPath.Size ()> rightPath.Size ()) กลับไปทางซ้าย อื่นกลับ RightPath; -

บทความข้างต้นค้นหาโหนดใบไม้ที่ไกลที่สุด (ตัวอย่างคำอธิบาย) ของทรีไบนารีเป็นเนื้อหาทั้งหมดที่ฉันแบ่งปันกับคุณ ฉันหวังว่ามันจะให้ข้อมูลอ้างอิงและฉันหวังว่าคุณจะสนับสนุน wulin.com มากขึ้น