- 在展平功能中，我無法理解遞回部分？？
2.當flatten return root（不是if部分）時，這里的root是如何接收的？
//下面是 flatten() 的代碼，它從節點的末尾開始。每個節點都有兩個指標 next 和 down 。這個函式將它們全部合并排序并回傳。最后附上完整代碼的幫助。
// Java program for flattening a Linked List
Node flatten(Node root) {
// Base Cases
if (root == null || root.right == null)
return root;
// recur for list on right
root.right = flatten(root.right);
// now merge
root = merge(root, root.right);
// return the root
// it will be in turn merged with its left
return root;
}
//完整的幫助代碼
//展平墨跡串列完整代碼
// 在 vs studio 中除錯
class LinkedList {
Node head; // head of list
/* Linked list Node */
class Node {
int data;
Node right, down;
Node(int data) {
this.data = data;
right = null;
down = null;
}
}
// An utility function to merge two sorted linked lists
Node merge(Node a, Node b) {
// if first linked list is empty then second
// is the answer
if (a == null)
return b;
// if second linked list is empty then first
// is the result
if (b == null)
return a;
// compare the data members of the two linked lists
// and put the larger one in the result
Node result;
if (a.data < b.data) {
result = a;
result.down = merge(a.down, b);
}
else {
result = b;
result.down = merge(a, b.down);
}
result.right = null;
return result;
}
Node flatten(Node root) {
// Base Cases
if (root == null || root.right == null)
return root;
// recur for list on right
root.right = flatten(root.right);
// now merge
root = merge(root, root.right);
// return the root
// it will be in turn merged with its left
return root;
}
/*
* Utility function to insert a node at beginning of the
* linked list
*/
Node push(Node head_ref, int data) {
/*
* 1 & 2: Allocate the Node &
* Put in the data
*/
Node new_node = new Node(data);
/* 3. Make next of new Node as head */
new_node.down = head_ref;
/* 4. Move the head to point to new Node */
head_ref = new_node;
/* 5. return to link it back */
return head_ref;
}
void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data " ");
temp = temp.down;
}
System.out.println();
}
// Driver's code
public static void main(String args[]) {
LinkedList L = new LinkedList();
L.head = L.push(L.head, 7);
L.head = L.push(L.head, 5);
L.head.right = L.push(L.head.right, 50);
L.head.right = L.push(L.head.right, 22);
L.head.right = L.push(L.head.right, 19);
L.head.right.right = L.push(L.head.right.right, 45);
L.head.right.right = L.push(L.head.right.right, 40);
L.head.right.right = L.push(L.head.right.right, 35);
L.head.right.right = L.push(L.head.right.right, 20);
// Function call
L.head = L.flatten(L.head);
L.printList();
}
uj5u.com熱心網友回復：
如果我理解正確，您想知道遞回在此代碼中是如何作業的。
1 Node flatten(Node root) {
2 // Base Cases
3 if (root == null || root.right == null)
4 return root;
5
6 // recur for list on right
7 root.right = flatten(root.right);
8
9 // now merge
10 root = merge(root, root.right);
11
12 // return the root
13 // it will be in turn merged with its left
14 return root;
15 }
假設我們的鏈表如下所示：
5 -> 10 -> 19 -> 28
| | | |
V V V V
7 20 22 35
| | |
V V V
8 50 40
| |
V V
30 45
現在，讓我們逐行遍歷這個方法。基本情況確保一旦我們到達最右邊的鏈表，它就會按原樣回傳。所以，現在因為我們將上面的鏈表傳遞給了這個根不為空并且右邊有另一個鏈表的函式，所以函式控制移動到第 7 行。在第 7 行，flatten(root.right)函式被呼叫。讓我們假設我們的理智，這個函式完全按照它應該做的事情，它將所有鏈表展平到它的右邊，我們將這個新展平的鏈表右邊部分分配給root.right.
現在，我們剩下的就是我們的基本鏈表5-7-8-30和它的右邊是扁平鏈表。所以，我們現在只需要合并這兩個并將其回傳，我們在第 10 行和第 14 行中所做的那樣。
如果你注意到上面的內容，我避免了在第 7 行考慮函式呼叫的兔子洞的麻煩。這簡化了遞回邏輯。
我們也可以遞回思考并得出相同的結論，因為對于每個后續flatten函式呼叫，merge都會發生并且根將回傳到上一個函式呼叫，該函式呼叫將分配給root.right父函式，然后合并并回傳其父函式呼叫并且將遵循相同的程序，直到控制元件到達鏈表的頭部，其中只有 2 個鏈表將保留在末尾，它們將被合并并回傳。
第三種方法可以借助函式呼叫堆疊圖直觀地理解這一點。稍后我會更新此答案，以便在我有時間時將其包含在內。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/504940.html
下一篇：在SQL中創建表時引發錯誤