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

Question

我试图通过自上而下的递归来实现二进制树的最低祖先（LCA）的解决方案。

我使用的方法是：

IDEA：找到一个子树中具有所需节点之一的节点，而另一个所需的节点是相反的子树。

PSEUDOCODE
1. If the value of root is equal to either of the desired node's value, 
   the root is the LCA.
2. Search in the left subtree for either node.
3. Search in the right subtree for either node.
4. If neither of them contains any of the two nodes,
   the nodes do not exist in the tree rooted at the root node.
5. If each of them contains one node,
   the root is the LCA.
6. If either one of them contains a node,
   return it to the root.

这也是在stackoverflow上的相关问题的答案中推荐的。
现在，如果我们假设树的所有节点具有独特的价值，则此代码效果很好。换句话说，这种方法似乎在重复的情况下打破了（或者，这只是我的实现吗？）

我想知道如何修复我的代码以使用重复值。如果这种方法无法产生最佳解决方案，我应该如何改变我的方法？

这是确切的实现：

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)))

这将返回树的根。 结果= treenode（2）

毫无疑问，根一直是祖先。
但是，存在比根-TreeNode(5)的"低"共同祖先。

Answer 1

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

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

您可能想从头开始重新考虑算法（您有一些不错的想法，但是现在您看到自己犯了一些错误，并且由于此问题相当简单/简单，因此要重新思考可能会更有益）。

一个建议：由于此问题是树上的问题，并且与搜索/路径有关，因此请考虑找到从节点P到节点Q的路径的问题。我们知道，在树上，从任何两个节点中都存在一条路径（这只是从一棵树是连接的无环形图的事实中遵循的）。

。

您可能会牢记这个想法，然后再递归后恢复基本案例，或者在递归到基本情况后您可能需要创建一个数据结构以将访问的节点存储在循环中，然后测试某些条件并可能重新浏览更多（本质上是DFS方法与BFS方法，而BFS方法使用明确的回忆/附加的内存，而DFS则使用堆栈来记住事物）。

Answer 2

代码看起来像

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

Answer 3

这个想法就是这样：我们在root的左右子树中递归搜索p和q。如果左子树的结果为null，则表示P和Q不在root的左边，因此我们可以安全地得出结论，LCA必须驻留在Root的右子树中。如果右子树的结果为无效，则类似的结论也是如此。但是，如果它们都不是零，则表明P和Q占根的两侧。因此，根是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;
        }
    }
}

Answer 4

var lowestCommonAncestor = function(root, p, q) { 
   
    const lca = (root) => {
        // Check if the root is the value, is yes then just return the root
        if (!root || root.val === p.val || root.val === q.val){
            return root;
        }
        // Traverse through left and right tree
        let L = lca(root.left);
        let R = lca(root.right);
        // If we have left and right node, which means val1 and val2 are on the either side of root,
        // then return root else return L or R
        if (L && R)
            return root;
        return L ? L : R;
    }
    return lca(root) || -1;
};