首页 文章

使用递归的二叉树中最低的共同祖先

提问于
浏览 次
1

我试图通过自上而下的递归实现二叉树最低共同祖先（LCA）的问题的解决方案 .

我使用的方法是：

IDEA：找到在任一子树中具有所需节点之一的节点，而另一个所需节点是相反的子树 . 伪代码
1.如果root的值等于所需节点的值，
根是LCA .
2.在左子树中搜索任一节点 .
3.在右侧子树中搜索任一节点 .
4.如果它们都不包含任何两个节点，
根节点中的节点不存在于根节点中 .
5.如果每个节点包含一个节点，
根是LCA .
6.如果其中任何一个包含节点，
将它返回到根目录 .

这也是StackOverflow上related questions的答案中推荐的内容 .
现在，如果我们假设树的所有节点都具有唯一值，则此代码可以正常工作 . 换句话说， this approach seems to break in case of duplicates （或者，它只是我的实现？）

我想知道如何修复我的代码以处理重复值 . 如果这种方法不能产生最佳解决方案，我该如何改变我的方法？

这是确切的实现：

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __repr__(self):
        return 'TreeNode({}, {}, {})'.format(self.val, self.left, self.right)

def lowestCommonAncestor(root, p, q):
    """
    :type root: TreeNode
    :type p: TreeNode
    :type q: TreeNode
    :rtype: TreeNode
    """
    if root is None:
        return None

    if p.val == root.val or q.val == root.val:
        return root

    left_subtree = lowestCommonAncestor(root.left, p, q)
    right_subtree = lowestCommonAncestor(root.right, p, q)

    if left_subtree is None and right_subtree is None:
        return None

    if left_subtree is not None and right_subtree is not None:
        return root

    if left_subtree is None:
        return right_subtree
    else:
        return left_subtree

例如：

root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(1)
root.right = TreeNode(5)
root.right.left = TreeNode(7)
root.right.right = TreeNode(1)
print(lowestCommonAncestor(root, TreeNode(1), TreeNode(7)))

这将返回树的根作为结果 . result = TreeNode（2）

毫无疑问，根始终是祖先 .
但是，存在"lower"共同祖先而不是根 - TreeNode(5) .

python algorithm recursion tree

3 回答

  • 0

    你有一些问题：1）你为什么要检查Node.val？您应该能够直接将一个节点与另一个节点进行比较 . 当你有一个具有多个具有相同值的节点的树时，这应该可以解决问题...假设这是你唯一的问题 .

    2）如果左子树非空并且右子树非空，为什么还要返回root？当然，在许多情况下，这将返回root . 这通常不是我们想要的行为 .

    你可能想从头开始重新思考你的算法（你有一些好的想法，但现在你发现你犯了一些错误，因为这个问题相当简单/直接，重新思考可能更有利） .

    一个建议：由于这个问题是树上的问题，并且与搜索/路径有关，请考虑查找从节点p到节点q的路径的问题 . 我们知道在树中，任何两个节点都只存在一条路径（根据定义，这只是树是一个连通的非循环图的事实） .

    在递归到基本案例之后返回时，或者在递归到基本案例之后，您可能会记住这个想法，您可能想要创建一个数据结构来存储循环中的访问节点然后测试一些条件并且可能更多地递归（基本上） DFS方法与BFS方法，而BFS方法使用显式memoization /添加内存，而DFS使用堆栈来记住事物） .

    回复于
  • 0

    代码看起来像这样

    def lowestCommonAncestor(root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
flag=0
if root is None:
    return None

if p.val == root.val or q.val == root.val:
    flag=1
    #return root

left_subtree = lowestCommonAncestor(root.left, p, q)
right_subtree = lowestCommonAncestor(root.right, p, q)

if left_subtree is None and right_subtree is None:
    if flag==0:
        return None
    else:
        return root

if left_subtree is not None and right_subtree is not None:
    return root

if left_subtree is None:
    if flag==1:
        if (right_subtree.value!=p && right_subtree.value!=q) || right_subtree.value==root.value:
            return right_subtree
        elif right_subtree.value!=root.value:
            return root
    else:
        return right_subtree
else:
    if flag==1:
        if (left_subtree.value!=p && left_subtree.value!=q) || left_subtree.value==root.value:
            return left_subtree
        elif left_subtree.value!=root.value:
            return root
    else:
        return left_subtree
    回复于
  • 0

    这个想法是这样的：我们在root的左右子树中递归搜索p和q . 如果左子树的结果为null，则表示p和q不在root的左侧，因此我们可以安全地断定LCA必须位于root的右子树中 . 如果右子树的结果为空，则类似的结论也适用 . 但如果它们都不为null，则表明p和q占据了根的任一侧 . 因此，root是LCA .

    class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }

        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right= lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }
}
    回复于

相关问题