python - LeetCode 236. 二叉树的最低共同祖先 - 回溯解决方案 - Python

Question

我正在研究这个问题（https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/），我试图用python中的回溯来解决它，这是我的逻辑：

• 遍历树并找到两个节点
• 返回他们的路径，然后找到出现在两个路径中的第一个元素，这将是 LCA

这是我的代码：

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.path_1 = []
        self.path_2 = []
        
        self.traverse(root, [], p, q)
        
        print(self.path_1, self.path_2)
        
        for val in self.path_1:
            if val in self.path_2:
                return val
        
    def traverse(self, node, path, p, q):
        if not node:
            return
        
        path.append(node.val)
        
        if node is p:
            self.path_1 = path
        
        if node is q:
            self.path_2 = path
        
        self.traverse(node.left, path, p, q)
        self.traverse(node.right, path, p, q)
        path.remove(node.val)

似乎回溯部分不起作用，它没有给我通往两个节点的路径。有人可以帮我解决如何解决此方法吗？我知道这个解决方案不是解决这个问题的最佳方法，但我想知道我在代码中的逻辑思维有什么问题。预先感谢！

标签： pythonalgorithmbinary-treebacktrackingtree-traversal