相关疑难解决方法(0)

我能够理解preorder遍历而不使用递归,但我很难进行inorder遍历.我也许似乎没有得到它,因为我还没有理解递归的内在工作.

这是我到目前为止所尝试的:

def traverseInorder(node):
    lifo = Lifo()
    lifo.push(node)
    while True:
        if node is None:
            break
        if node.left is not None:
            lifo.push(node.left)
            node = node.left
            continue
        prev = node
        while True:
            if node is None:
                break
            print node.value
            prev = node
            node = lifo.pop()
        node = prev
        if node.right is not None:
            lifo.push(node.right)
            node = node.right
        else:
            break

内部的while循环感觉不对劲.此外,一些元素被打印两次; 也许我可以通过检查之前是否打印过该节点来解决这个问题,但这需要另一个变量,这也是感觉不对.我哪里错了？

我没有尝试过postorder遍历,但我猜它类似,我也将面临同样的概念障碍.

谢谢你的时间!

PS:Lifo和的定义Node:

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

基于该答案,这里有两个版本的merge函数用于mergesort.你能帮我理解为什么第二个更快.我已经测试了它的50000列表,第二个测试速度提高了8倍(Gist).

def merge1(left, right):
    i = j = inv = 0
    merged = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            inv += len(left[i:])

    merged += left[i:]
    merged += right[j:]
    return merged, inv

.

def merge2(array1, array2):
    inv = 0
    merged_array = []
    while array1 or array2:
        if not array1:
            merged_array.append(array2.pop())
        elif (not array2) or array1[-1] > array2[-1]:
            merged_array.append(array1.pop())
            inv += len(array2) …