Morris遍历-如何检查是否达到叶节点？

Question

在二叉树的morris遍历中，它使用每个右叶节点建立指向当前节点的连接。

假设我们以预先排序的方式遍历树，当到达叶节点时，我们如何判断是否遇到叶节点？

我们不能使用下面的行来检查：if（null==node.left

因为这里node.right指向当前节点，因为莫里斯算法。

一个好方法是，我们总是使用TreeNode对象中的一个字段将访问的节点标记为已访问，但是如果我们没有这个字段，在许多情况下会怎么样？

有人知道如何检查你是否到达叶节点吗？谢谢。

你好，杰克

Answer 1

通过标记已访问的节点，可以简单地解决问题。

因此，叶节点可以通过以下方式来证明：if（null==node.left

好吧，又回到我的问题上来了，我们怎么能有这张关于“isLinked”的唱片呢？

我们可以通过设置一个集合来添加所有morris链接节点来轻松解决此问题。

所以它会是：如果（（null==node.left

Answer 2

更新：我想出了关于如何使用Morris遍历检测叶节点的更清晰的解释。所有的叶子是：

1. 只有一片叶子是树上最合适的。要检测它，您需要检查curr left==nil和curr。右==零
2. 其余所有的叶子都是人工设置链接到其他节点的叶子。仔细想想，这是有道理的：Morris Traversal不能以任何其他方式从叶节点回溯。因此，所有剩余的leaf都是连接到当前节点的前置节点

如果对您来说仍然没有意义，请查看此Morris遍历的可视化，并注意除一个叶外，所有叶都是“连接”节点，一个位于树的最末端：

这很棘手，但有可能，这是Go中的代码，我用大量棘手的边缘情况进行了测试，同时仍然保持O（1）：

func getLeafs(node *TreeNode) []int {
    var leafs []int
    var pre *TreeNode // predecessor of the current node
    curr := node

    for curr != nil {
        if curr.Left == nil {
            if curr.Right == nil { // additional check needed
                leafs = append(leafs, curr.Val)
            }
            curr = curr.Right
            continue
        }

        // curr.Right != nil
        pre = curr.Left
        for pre.Right != nil && pre.Right != curr {
            pre = pre.Right
        }

        if pre.Right == nil {
            pre.Right = curr
            curr = curr.Left
            continue
        }

        // pre.Right == curr
        pre.Right = nil
        if pre.Left == nil { // tricky part! we are not using curr here
            leafs = append(leafs, pre.Val)  // we are actually using pre
        }
        curr = curr.Right
    }

    return leafs
}

基本上，您需要在两个地方进行检查：

1. 与标准的Morris遍历一样，检查curr。左==nil，然后curr。右==nil
2. 棘手的部分：不是使用curr，而是需要使用前节点，当它们具有到curr节点的链接时。

Answer 3

就像Jack回答的那样，检查（null==node.left

在这里分享我的代码

def getLeaf(self, root):
    curr = root
    while curr != None:
        if not curr.left and (not curr.right or hasattr(curr, 'isLinked')):
            print("I am a leaf ", curr.val)
        if curr.left is None:
            curr = curr.right
        else:
            prec = curr.left
            while prec.right != None and prec.right != curr:
                prec = prec.right
            if prec.right is None:
                prec.right = curr
                setattr(prec, 'isLinked', True)
                curr = curr.left
            else:
                curr = curr.right