二维数组递归到二维双向链表

Question

给定一个二维数组，仅使用递归创建一个二维双向链表。列表中的每个数字都必须有 4 个指针（上、下、右、左），并且需要链接到它旁边的每个数字（如果没有数字，则只是 'None'）

import numpy as np

class Node:

""" Node class
    
        up
         |
left - data - right
         |
       down
"""

   def __init__(self, data):
       self.data = data
       self.right = None
       self.left = None
       self.up = None
       self.down = None

def constructDoublyLinkedListRecursion(arr):

    """ Converts a 2D array into a 2D doubly linked list by calling
    the recursee constructDLLRecursiveStep.
 
    input:
        arr: 2D array to turn into a 2D DLL
        
    output:
        head (top left node) of the 2D DLL of the input arr.
    """
    return constructDLLRecursiveStep(arr, 0, 0, None)

def constructDLLRecursiveStep(arr, y, x, curr):
    """ Recursively construct the 2D DLL from the given array.
    This is the "recursee" of constructDoublyLinkedListRecursion.
    
    input:
        arr: The 2D array to construct the 2D DLL from.
        y: y-coordinate of the array to get the value from.
        x: x-coordinate of the array to get the value from.
        curr: The current node to connect the new node from.
        
    output:
        new_node: The newly created node which connects to curr node.
    """
        
    return new_node

这是我目前所做的：

def constructDLLRecursiveStep(arr, y, x, curr):
    
    arrDim = arr.shape[1]
    
    if(y >= arrDim or x >= arrDim):
        return None;
    
    new_node = Node(arr[y,x])
        
    if(x > 0):
        new_node.left = curr
    else:
        new_node.left = None
        
    if(y > 0):
        new_node.up = curr
    else:
        new_node.up = None
    
    new_node.right = constructDLLRecursiveStep(arr, y, x+1, new_node)
    
    new_node.down = constructDLLRecursiveStep(arr, y+1, x, new_node)
    
    return new_node

显示功能

def display(dll_ptr):
    """ Prints the 2D dll according to their positions similar to 
        printing a 2D array.
    
    input:
        dll_ptr: the head (most upper left node) of a 2D dll.
        
    output:
        None
    """
    right_ptr = None
    down_ptr = dll_ptr
    
    while down_ptr != None:
        right_ptr = down_ptr
        
        while right_ptr != None:
            msg = f"{right_ptr.data} | "
            for i, direction in enumerate([("up", right_ptr.up), ("right", right_ptr.right), ("down", right_ptr.down), ("left", right_ptr.left)]):
                direction_str, direction_ptr = direction
                if direction_ptr: msg += f"{direction_str}: {direction_ptr.data}"
                else: msg += f"{direction_str}: None"
                msg += ", "
            print(msg) 
            right_ptr = right_ptr.right
        print()
        down_ptr = down_ptr.down

我得到的输出表明向上指针存在问题：

"""
Input 2D array:
[[9 4 0 8 6]
 [4 3 2 2 7]
 [9 7 3 9 2]
 [8 7 3 6 2]
 [9 4 6 5 3]]
<class 'numpy.ndarray'>

constructDoublyLinkedListRecursion output:
9 4 0 8 6 
4 3 2 2 7
9 7 3 9 2
8 7 3 6 2
9 4 6 5 3

constructDoublyLinkedListRecursion output:
9 | up: None, right: 4, down: 4, left: None, 
4 | up: None, right: 0, down: 3, left: 9, 
0 | up: None, right: 8, down: 2, left: 4, 
8 | up: None, right: 6, down: 2, left: 0, 
6 | up: None, right: None, down: 7, left: 8, 

4 | up: 9, right: 3, down: 9, left: None, 
3 | up: 4, right: 2, down: 7, left: 4, 
2 | up: 3, right: 2, down: 3, left: 3, 
2 | up: 2, right: 7, down: 9, left: 2, 
7 | up: 2, right: None, down: 2, left: 2, 

9 | up: 4, right: 7, down: 8, left: None, 
7 | up: 9, right: 3, down: 7, left: 9, 
3 | up: 7, right: 9, down: 3, left: 7, 
9 | up: 3, right: 2, down: 6, left: 3, 
2 | up: 9, right: None, down: 2, left: 9, 

8 | up: 9, right: 7, down: 9, left: None, 
7 | up: 8, right: 3, down: 4, left: 8, 
3 | up: 7, right: 6, down: 6, left: 7, 
6 | up: 3, right: 2, down: 5, left: 3, 
2 | up: 6, right: None, down: 3, left: 6, 

9 | up: 8, right: 4, down: None, left: None, 
4 | up: 9, right: 6, down: None, left: 9, 
6 | up: 4, right: 5, down: None, left: 4, 
5 | up: 6, right: 3, down: None, left: 6, 
3 | up: 5, right: None, down: None, left: 5, 
"""

Answer 1

主要问题是你几乎无条件地在两个方向上重复出现。这意味着索引 1, 1 处的节点将通过两个不同的递归路径创建：一次是首先使用 x + 1 重复，然后使用 y + 1，第二次是在调用 y + 1 时递归使用 x + 1 进行调用。递归调用的总数远远超过您真正需要创建的节点数，因为正在创建通过矩阵的所有可能 (zig-zag) 路径。

一种解决方案是仅在 x 为零时使用 y + 1 进行递归调用。这将启动创建整行的过程（使用 x + 1 递归）。唯一需要注意的是将这些节点“nit”到它们上方的相应节点。但是你可以通过从左边的节点向上走然后走右边的节点来实现。

这是更正后的代码：

def constructDLLRecursiveStep(arr, y, x, curr):
    leny, lenx = arr.shape
    if y >= leny or x >= lenx: 
        return None

    new_node = Node(arr[y,x])
    if x == 0: # Came from above
        new_node.up = curr
    else: # Came from the left
        new_node.left = curr
        if y > 0: # Link to row above, by walking "the block"
            curr.up.right.down = new_node
            new_node.up = curr.up.right

    new_node.right = constructDLLRecursiveStep(arr, y, x + 1, new_node)
    if x == 0: # Recur downwards
        new_node.down = constructDLLRecursiveStep(arr, y + 1, 0, new_node)
    return new_node

二维数组递归到二维双向链表

2D array to 2D doubly linked list by recursion

python

doubly-linked-list