ให้ต้นไม้ไบนารีค้นหาเส้นทางที่ผลรวมของแต่ละโหนดในทุกเส้นทางเท่ากับค่าเป้าหมายที่กำหนด
เส้นทางที่ถูกต้องหมายถึงเส้นทางจากโหนดรูทไปยังโหนดใบ
ตัวอย่าง
กำหนดต้นไม้ไบนารีและค่าเป้าหมาย = 5:
1 / / 2 4 / / 2 3
กลับ:
[[1, 2, 2], [1, 4]]
รหัสมีดังนี้:
/** * คำจำกัดความของ Treenode: * คลาสสาธารณะ treenode { * public int val; * สาธารณะ treenode ซ้ายขวา; * สาธารณะ treenode (int val) { * this.val = val; * this.left = this.right = null; *} *} */โซลูชันคลาสสาธารณะ {/** * @param รูทรากของทรีไบนารี * @param กำหนดเป้าหมายจำนวนเต็ม * @กลับมาเส้นทางที่ถูกต้องทั้งหมด */รายการสาธารณะ <รายการ <จำนวนเต็ม >> binarytreepathsum (treenode root, int target) {// เขียนรหัส arraylist <list <integer> (), target);} รายการสาธารณะ <list <integer>> dfs (treenode root, รายการ <จำนวนเต็ม> โหนด, ผลรวม int, รายการ <รายการ <จำนวนเต็ม >> เส้นทาง, int เป้าหมาย) {ถ้า (root == null) {ส่งคืน arrayList <list <integer >> (); if (root.left! = null) {list <teeger> nodes = new ArrayList <Integer> (); ถ้า (Node! = NULL) {nodes.addall (Node);} nodes.add (root.val); temp = dfs (root.left, โหนด, sum+root.val, เส้นทาง, เป้าหมาย); ถ้า (temp! = null) {path.addall (temp);}} ถ้า (root.right! = null) {รายการ <teger> nodes = new ArrayList <Integer> () {nodes.addall (node);} nodes.add (root.val); รายการ <รายการ <จำนวนเต็ม >> temp = dfs (root.right, โหนด, sum+root.val, เส้นทาง, เป้าหมาย); ถ้า (temp! = null) {path.addall (temp); NODES = New ArrayList <Integer> (); ถ้า (Node! = NULL) {nodes.addall (Node);} nodes.add (root.val); ถ้า (sum+root.val == เป้าหมาย) {path.add (โหนด);อ้างอิง
การวิเคราะห์รหัสของปัญหาการค้นหาเส้นทางสูงสุดของทรีไบนารีในการเขียนโปรแกรม Java
การวิเคราะห์รหัสทดสอบมรดกใน Java
สรุป
ข้างต้นเป็นเรื่องเกี่ยวกับเส้นทางต้นไม้ไบนารีจาวาและตัวอย่างรหัสในบทความนี้ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!