二叉树 - 从最后一层遍历到根的最优雅的方式

Question

我正在寻找一个允许我遍历二叉搜索树的实现，从最后一层开始从左到右到根，例如：

                 A
               B   C
             D  E    G

应该return：[D, E, G, B, C, A]。我对递归方法或迭代方法都感兴趣。

Answer 1

我不确定我在 Python 中的解决方案是否足够优雅，但也许它会有所帮助。

简介

让我们考虑一个例子如下：

                   8
                 /   \
                5    10
               / \     \  
              4   6    12

预期输出为 4, 6, 12, 5, 10, 8。但是如何实现呢？

步骤 1 - BFS

让我们做一个稍作修改的 BFS - 首先遍历右侧 child，然后遍历左侧。

def bfs(node):
    q  = []
    q.append(node)
    while q:
        current = q.pop(0)
        print (current.value, end = ' ')
        if current.right:
            q.append(current.right)
        if current.left:
            q.append(current.left)

输出结果如下：

8, 10, 5, 12, 6, 4

输出基本上与预期输出相反！

第 2 步 - 反向 BFS 输出

为此，引入一个保存队列当前元素的堆栈变量。

def bfsFromBottomToTop(node):
    q  = []
    q.append(node)
    st = [] # create a stack variable
    while q:
        current = q.pop(0)
        st.append(current.value) # push the current element to the stack
        if current.right:
            q.append(current.right)
        if current.left:
            q.append(current.left)

然后，您可以在方法结束时将所有元素弹出堆栈，如下所示：

    ...
    while st:
        print(st.pop(), end = ' ')
    ...

4 6 12 5 10 8

完整代码

下面是完整的代码，您可以自己尝试一下。

class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value

def insert(node, value):
    if node is None:
        return Node(value)

    if node.value > value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)

    return node

def bfsFromBottomToTop(node):
    q  = []
    q.append(node)
    st = []
    while q:
        current = q.pop(0)
        st.append(current.value)
        if current.right:
            q.append(current.right)
        if current.left:
            q.append(current.left)

    while st:
        print(st.pop(), end = ' ')

root = Node(8)
insert(root, 5)
insert(root, 10)
insert(root, 6)
insert(root, 4)
insert(root, 12)
bfsFromBottomToTop(root)

二叉树 - 从最后一层遍历到根的最优雅的方式

Binary Tree - Most elegant way to traverse from the last level to root

algorithm

breadth-first-search

binary-search-tree

简介

步骤 1 - BFS

第 2 步 - 反向 BFS 输出

完整代码