二叉树：第一个共同的祖先-Java 学习之路

在过去的几天里，我一直在为树木和蟒蛇而苦苦挣扎 . 大多数情况下，树木的递归给我带来了麻烦 . 我试图解决的问题是在二叉树中找到第一个共同的祖先 . 有很多解决方案可以解决这个问题，但它们都是二叉搜索树，而不是二叉树 . 在二叉树的情况下，节点不是有序的，因此左边小于右边 . 我知道我应该使用哪种方法，但我在递归部分失败:(编辑：问题表明我不能使用额外的数据结构或存储）

class Node:

    """docstring for Node"""
    def __init__(self, data):
        self.data = data
        self.left=None
        self.right=None

def findNode(self,target):
    if self==None:
        return 0
    if self.data==target:
        return 1
    return self.findNode(self.left,target) or self.findNode(self.right,target)

def firstCommonAncestor(self,p,q):
    if self==None:
        return 0
    if self.left.data==p and self.right.data==q:
        return self.data
    if findNode(self.left,p) and findNode(self.right,q):
       return 1

root=Node(2)
root.left=Node(5)
root.right=Node(4)
root.left.left=Node(9)
root.left.right=Node(7)
print firstCommonAncestor(root,9,7)

我编辑了代码以使问题更加清晰 . findNode（self.left，p）和findNode（self.right，q）应返回1，因为两个节点都存在 . 但是，当findNode（self.right，q）没有从根开始搜索时 . 我知道我应该实现递归调用，但我尝试过的所有内容都失败了 . 如果有人可以就我的错误提供一些指示，我们将不胜感激！（第一个共同的祖先尚未实施，所以这并不重要 . 现在它没有做太多事情） . 编辑：这是破解编码面试的一个问题 .

5 回答

-1
（只是为了暗示它为什么不起作用）

搜索y时，它不会返回到根目录 . 你的代码正在做正确的事情 . 您找不到Node（7）的原因是您的数据 .

这是你的树 .
```
2
         |
      -------
     5       4
  -------
  9     7
```
你的x搜索是findNode（Node（5），9），它找到9 .

你的y搜索是findNode（Node（4），7），当然它永远不会找到7

希望有所帮助 .
回复于 2024-04-20T07:37:28+08:00

-1

另一个提示：你的实例方法脱离了类，并且只是普通的全局方法（它不仅仅是缩进的问题，因为你也以错误的方式调用它们） . 这是 findNode 的正确定义：

class Node:

    """docstring for Node"""
    def __init__(self, data):
        self.data = data
        self.left=None
        self.right=None

    def findNode(self,target):
        result = None

        if self.data == target:
            return self

        result = self.left.findNode(target) if self.left else None
        if not result:
            result = self.right.findNode(target) if self.right else None

        return result

    def firstCommonAncestor(self, p, q):
        pass #TODO

在 findNode 方法中，您还有一个如何调用它的示例 . 您还应该在 firstCommonAncestor 方法中修复此问题 .

回复于 2024-04-20T07:37:28+08:00

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

    def isAncestor(self, p, q):
        ret = 0
        if self.data == None:
            return ret
        if (self.data == p):
            ret += 1
        if self.data == q:
            ret += 1
        if ret == 2:
            return ret
        if self.left!=None:
            ret += self.left.isAncestor(p, q)
        if ret == 2:
            return ret
        if self.right!=None:
            return ret + self.right.isAncestor(p ,q)
        return ret

    def commonAncestor(self, p, q):
        if q == p and (self.left.data == q or self.right.data == q):
            return self
        lNodes = self.left.isAncestor(p, q)
        if lNodes == 2:
            if self.left.data == p or self.left.data == q:
                return self.left
            else:
                return self.left.commonAncestor(p, q)
        elif lNodes == 1:
            if self.data == p:
                return p
            elif self.data == q:
                return q

        rNodes = self.right.isAncestor(p, q)
        if rNodes == 2:
            if self.right.data == p or self.right.data == q:
                return self.right
            else:
                return self.right.commonAncestor(p, q)
        elif rNodes == 1:
            if self.data == p:
                return p
            elif self.data == q:
                return q

        if lNodes == 1 and rNodes ==1:
            return self
        else:
            return None


"""
             2
           /   \
          5     4
        /  \   /  \
       9    7     11
                    \
                    12
"""
if __name__ == '__main__':
    root=Node(2)
    root.left=Node(2)
    root.right=Node(4)
    root.right.right=Node(11)
    root.left.left=Node(9)
    root.left.right=Node(7)
    root.right.right.right=Node(12)
    common = root.commonAncestor(2,2)
    if common != None:
        print common.data
    else:
        print "Not found"

回复于 2024-04-20T07:37:28+08:00

由于树没有订购，你无论如何都要搜索很多 . 由于您不允许使用额外的数据结构，因此您可能会重复进行大量搜索 .

因此，一旦递归到叶节点，然后在返回组合数据上，这可能是最有效的 . 这是O（n），但那么一次搜索也是如此 .

这就是下面的代码试图做的事情 . 搜索方法返回 (a's parent, b's parent) ，如果它们不同，但两者都设置了，那么我们就是共同的祖先 .

def search(self, a, b):
    ap1 = ap2 = ap3 = bp1 = bp2 = bp3 = None
    # parents to left
    if self.left:
        ap1, bp1 = self.left.search(a, b)
    # parents to right
    if self.right:
        ap2, bp2 = self.right.search(a, b)
    # are we an immediate "parent" ourselves?
    if self.data == a: 
        ap3 = self
    elif self.data == b:
        bp3 = self
    # only one of the above can succeed, so find it
    ap = ap1 or ap2 or ap3
    bp = bp1 or bp2 or bp3
    # if we are the point where two paths meet at the common
    # ancestor, return ourselves
    if ap and bp and ap != bp:
        return self, self
    # otherwise, return what we have
    else:
        return ap, bp

回复于 2024-04-20T07:37:28+08:00

EDIT : 重新设计的解决方案使其更清晰并解决了评论中的问题

有一个非常有效的解决方案，但有点复杂 . 它涉及钻入树中并跟踪您是否在返回时找到了第一个或第二个值 . 如果在某些时候你发现两个（第一个和第二个）都返回该节点，它将是你的共同祖先 .

这是一个更有效的解决方案，但是如果你有DUPLICATES它不起作用，但它可以帮助你理解并解决重复的情况：

class Node:
    """docstring for Node"""
    def __init__(self, data):
        self.data = data
        self.left=None
        self.right=None

    def union(self, u1, u2):
        res = u1[0] or u2[0], u1[1] or u2[1], u1[2] or u2[2]
        if res[0] and res[1] and not res[2]:
            return res[0], res[1], self
        return res

    def doCommon(self, p, q):
        # recursion base case
        l = (False, False, None)
        r = (False, False, None)
        if self.left:
            l = self.left.doCommon(p, q)
        if self.right:
            r = self.right.doCommon(p, q)

        res = self.union(l, r)
        if res[0] and res[1]:
            return res

        if self.data == p:
            return self.union((True, False, None), res)
        if self.data == q:
            return self.union((False, True, None), res)
        return res

    def common(self, p, q):
        return self.doCommon(p, q)[2]



if __name__ == '__main__':
    root=Node(2)
    root.left=Node(5)
    root.right=Node(4)
    root.left.left=Node(9)
    root.left.right=Node(7)
    res = root.common(9,7)
    if res != None:
        print res.data
    else:
        print "Not found"

回复于 2024-04-20T07:37:28+08:00

二叉树：第一个共同的祖先

5 回答

相关问题