将二叉树转换为双向链表（微软面试）

Question

我们正在将二叉树转换为 DLL，我们也正在使用顺序遍历来做到这一点。

在此处阅读更多内容 - Link

我的代码：

class BinaryTree():
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

def btToDll(node,head):

    prev = None
    return getbtToDll(node,head,prev)

def getbtToDll(node,head,prev):

    if node is None:
        return
    getbtToDll(node.left,head,prev)

    if prev is None:
        head = node
    else:
        node.left = prev
        prev.right = node
    prev = node

    getbtToDll(node.right,head,prev)


def printList(head):
    if head is None:
        print("NO LL FOUND AT THIS NODE")
    else:
        temp = head
        while(temp):
            print(temp.data)
            temp = temp.right


root = BinaryTree(10)
root.left = BinaryTree(12)
root.right = BinaryTree(15)
root.left.left = BinaryTree(25)
root.left.right = BinaryTree(30)
root.right.left = BinaryTree(36)

head = None
head1 = btToDll(root,head)

printList(head1)

我的问题： 头部始终是 None，因此我无法打印转换后的列表。这段代码或我的逻辑有什么问题？

Answer 1

你的代码有很多陷阱，主要原因是 return none 是因为从 btToDll return 什么都没有，而且它没有改变值头部，它仍然 None.

与其尝试修复您的代码，我更愿意一次性采用不同的方法。

基本上，我找到了一个获得结果的技巧：

向下移动到最左边的节点，它成为 HEAD。
检查是否从头开始你可以向上一个，然后向左-向左。或向上一右右等等。如果可以向左移动，则将当前节点设置为左下节点。这样做直到没有任何节点。在 DLL 列表中添加 Previous 节点
计算当前节点，它的前一个节点和前一个节点的右节点。
从二叉树返回，到达根节点（10），重复相同的模式。

你会看到，基本上，如果在任何给定的子节点中，有一个左节点，那么你计算整个三角形，最重要的节点永远是左节点，成为当前节点。如果左节点不存在，则父节点成为当前节点，则需要检查父节点是否没有右节点。

我准备了一些图片，形象化比解释要好得多。

取这个二叉树：

第一步 |尽可能转到最左边的节点

第二步 |计算第一个三角

注意：如果Right bottom Node (30)有一个left child node，那么30不会被添加，这个例子就是这样，而是去到下一步。

第 3 步 |转到Child的子节点的下一个Triangle步骤##

第 4 步 |现在上到根节点，计算左边的BT

注: 看到这个算法的完整路径，我又想象了多少个小三角形是分开计算的。

源代码

注意： 很长，但我是即时完成的，可以改进。

class BinaryTree():
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.prev = None
        self.visited = False

    def create_tree(self, show_tree=False):
        """Creating the Tree with a Depth-First Search Algorithm"""
            
        root = self # Set Current Node        
        stack = [root]

        while True:

            if not stack:
                break

            current = stack.pop() # Remove Current From Stack

            if current.right:
                current.right.prev = current
                stack.append(current.right)            
            if current.left:
                current.left.prev = current
                stack.append(current.left)

            if show_tree:
                print(f'{current.data} --> ', end='')


def create_dll(root_head):
    """Algorithm to Conver Binary Tree to Doubly Linked List"""

    doubly_linked_list = []

    # --- Find DLL Head NOTE: Just need to go left from Binary Tree till hit NONE
    head = None
    current = root_head 
    while True:
        if current.left:
            current = current.left
        else:
            head = current       
            break
    
    stack = [head]
    visited = set()

    def add_node(*args, add_dll=None):
        """Helper Function, Add Node to the Visited Set."""
        for item in args:
            visited.add(item)
        if add_dll:
            for node in add_dll:
                doubly_linked_list.append(node)

    # --- Crawls back up, following each Triangle Shape from left Vertices to Right
    while True:

        try:
            current = stack.pop()
        except IndexError:
            pass

        if current in doubly_linked_list:
            break
        
   
        if current.left and current.left not in visited: # NOTE: Goes Down to Next Triangle Shape        
            stack.append(current.left)
            continue
        elif current.prev: # NOTE: Goes Up one Node
            add_node(add_dll=[current])

            # ---------------  Check if we can go to the left.
            if current.prev.right.left and current.prev.right.left not in visited: # NOTE: Goes deeper 
                add_node(current.prev, current.prev.right, add_dll=[current.prev])

                if current.prev.prev: # NOTE: Backtracking
                    stack.append(current.prev.prev)
                stack.append(current.prev.right.left)    
                continue

            # ------------- Here We Handle in case previous Node Has ONLY Right path
            elif current.prev.right.right:  
                if current.prev.right.right.left:  # If has Left Node we go deeper
                    stack.append(current.right.right.left)    
                    continue
                add_node(add_dll=[current.prev.right.right])              
            else:     
                add_node(current.prev, add_dll=[current.prev])

                if current.prev.right: # DOES the Prev node have a Right node?
                    add_node(current.prev.right, add_dll=[current.prev.right])
                
        
                if current.prev.prev and current.prev.prev not in visited: # NOTE: BackTrackin
                    stack.append(current.prev.prev)
        #  -------------- >N OTE: Here Handle The 'Root node' (i.e. 10), only option is to go to right
        elif current.right: 
            add_node(current, add_dll=[current])
            if current.right.left: # Going Deeper
                stack.append(current.right.left)    
                continue
            elif current.right.right:   
                if current.right.right.left:
                    stack.append(current.right.right.left)    
                    continue
                add_node(current.right, current.right.right, add_dll=[current.right, current.right.right])                
            else:    
                add_node(current.right, add_dll=[current.right])  
    
    return doubly_linked_list

    
def show_ddl(ddl):
    """Helper function, used to print the Doubly Linked List"""
    for node in ddl:
        print(f'{node.data} --> ', end='')


# --------->  Creating The Binary Tree >

root = BinaryTree(10)
root.left = BinaryTree(12)
root.right = BinaryTree(15)
root.left.left = BinaryTree(25)
root.left.right = BinaryTree(30)
root.left.right.left = BinaryTree(60)           
root.left.right.right = BinaryTree(77)
root.right.right = BinaryTree(40)
root.right.left = BinaryTree(36)
root.right.left.left = BinaryTree(50)
root.right.left.right = BinaryTree(13)

print('\nBynary Tree:\n')
root.create_tree(show_tree=True)
print()
print('==='*15)
print()
# --------->  Creating The Doubly Linked List >
print('Doubly Linked List:\n')
dll = create_dll(root)
show_ddl(dll)

输出

Bynary Tree:

10 --> 12 --> 25 --> 30 --> 60 --> 77 --> 15 --> 36 --> 50 --> 13 --> 40 -->
=============================================

Doubly Linked List:

25 --> 12 --> 60 --> 30 --> 77 --> 10 --> 50 --> 36 --> 13 --> 15 --> 40 -->

将二叉树转换为双向链表（微软面试）

Covert Binary Tree to Doubly Linked List (Microsoft Interview)

python

binary-tree

linked-list

python-3.x

第一步 |尽可能转到最左边的节点

第二步 |计算第一个三角

第 3 步 |转到Child的子节点的下一个Triangle步骤##

第 4 步 |现在上到根节点，计算左边的BT

源代码

输出