LeetCode 236 树节点题， 疑问点在list的pop过程

236. Lowest Common Ancestor of a Binary Tree
找出两个节点的公共祖先
我遇到的问题是
首先我遍历搜索得到 path=[3,5]
然后我用深度复制result = copy.deepcopy(path)
接着我对path.pop()操作
但是这个时候我发现 path=[3].而result=[]. result的值太怪了，因为我已经深度复制了啊，应该是不变的，我不知道为什么，求各位大佬解答。谢谢

下面是我的代码：

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

import copy
class Solution:
    def lowestCommonAncestor(self, root, p, q):
        path = []
        node_p_path = []
        node_q_path = []
        finish = 0
        self.preorder(root, p, path, node_p_path, finish)
        path = []
        finish = 0
        self.preorder(root, q, path, node_q_path, finish)
        path_len = 0
        if len(node_p_path) < len(node_q_path):
            path_len = len(node_p_path)
        else:
            path_len = len(node_q_path)
        result = TreeNode(0)
        for i in range(path_len):
            if node_p_path[i] == node_q_path[i]:
                result = node_p_path[i]
        return result.val

    def preorder(self, node, search, path, result, finish):
        if not node or finish == 1:
            return
        path.append(node.val)
        if node.val == search.val:
            finish = 1
            result = copy.deepcopy(path)
        self.preorder(node.left, search, path, result, finish)

        self.preorder(node.right, search, path, result, finish)
        path.pop()


a=TreeNode(3)
b=TreeNode(5)
c=TreeNode(1)
d=TreeNode(6)
e=TreeNode(2)
f=TreeNode(0)
x=TreeNode(8)
y=TreeNode(7)
z=TreeNode(4)
a.left=b
a.right=c
b.left=d
b.right=e
c.left=f
c.right=x
e.left=y
e.right=z
x=Solution()
print(x.lowestCommonAncestor(a,b,f))

李冬冬 发表于 2019/06/03 14:48:57


有点明白了，但是该如何去改这个问题？在递归自程序里return这个值？万分感谢

我觉得return的方式更好，不过也可以尝试把result设为类的attribute（self.result），类似全局变量的感觉

半夜睡不着看到悬赏精神了答一下。。。大概看了看，如有不对还请指正
先说结论，不是deep copy的问题，是参数传递
python 是传引用的，楼主最开始传入result参数，假设引用是A，然后deepcopy，递归子程序中的result引用被改成了B，也就导致了最初传入的引用A的数据其实并没有改变，而最后楼主输出的正式这个A的result，所以依然是空的，而至于B的内容，已经随着层层递归的结束而被销毁了
楼主可以分别在对应位置print(id(result))来查看，应该会好理解些

Jarvet 发表于 2019-6-3 14:17
半夜睡不着看到悬赏精神了答一下。。。大概看了看，如有不对还请指正
先说结论，不是deep copy的问题，是 ...

有点明白了，但是该如何去改这个问题？在递归自程序里return这个值？万分感谢

Jarvet 发表于 2019-6-3 11:05
我觉得return的方式更好，不过也可以尝试把result设为类的attribute（self.result），类似全局变量的感觉

如下是我改的，还是不行，求帮忙改一下（捂脸），感激
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

import copy
class Solution:
    resultpath = []
    def lowestCommonAncestor(self, root, p, q):
        path = []
        node_p_path = []
        node_q_path = []
        finish = 0
        self.preorder(root, p, path, node_p_path, finish)
        path = []
        finish = 0
        self.preorder(root, q, path, node_q_path, finish)
        path_len = 0
        if len(node_p_path) < len(node_q_path):
            path_len = len(node_p_path)
        else:
            path_len = len(node_q_path)
        result = TreeNode(0)
        for i in range(path_len):
            if node_p_path[i] == node_q_path[i]:
                result = node_p_path[i]
        return result.val

    def preorder(self, node, search, path, resultpath, finish):
        if not node or finish == 1:
            return
        path.append(node.val)
        if node.val == search.val:
            finish = 1
            self.resultpath = copy.deepcopy(path)
        self.preorder(node.left, search, path, self.resultpath, finish)
        self.preorder(node.right, search, path, self.resultpath, finish)
        path.pop()

李冬冬 发表于 2019-6-3 14:48
有点明白了，但是该如何去改这个问题？在递归自程序里return这个值？万分感谢

return我改成了如下，还是不行。。。求解答
    def preorder(self, node, search, path, resultpath, finish):
        if not node or finish == 1:
            return
        path.append(node.val)
        if node.val == search.val:
            finish = 1
            resultpath = copy.deepcopy(path)
            return resultpath
        self.preorder(node.left, search, path, resultpath, finish)
        self.preorder(node.right, search, path, resultpath, finish)
        path.pop()

李冬冬 发表于 2019/06/04 13:25:36


return我改成了如下，还是不行。。。求解答
    def preorder(self, node, search, path, resultpath, finish):
        ...

你的第一个return没返回东西

补充内容 (2019-6-4 14:23):
其他的不太好描述…其实可以单靠return不用path和resultpath的，左右preorder的结果如果都存在，那就一定是当前节点，如果只存在一个，那就在存在的这一侧，大概是这样的思路，感觉path好像有点点多余…楼主思路是？

补充内容 (2019-6-4 14:28):
字数不够了，楼主思路是两边都搜到头然后再找对么，那样的话现在这样好像逻辑有些混乱了。。第一preorder的结果并没有return出来，第二分别搜时间上会很慢…

Jarvet 发表于 2019-6-4 14:11
你的第一个return没返回东西

补充内容 (2019-6-4 14:23):

还是没用啊，求教   
def preorder(self, node, search, path, resultpath, finish):
        if not node or finish == 1:
            return resultpath
        path.append(node.val)
        if node.val == search.val:
            finish = 1
            resultpath = copy.deepcopy(path)
        self.preorder(node.left, search, path, resultpath, finish)
        self.preorder(node.right, search, path, resultpath, finish)
        path.pop()

Jarvet 发表于 2019-6-4 14:11
你的第一个return没返回东西

补充内容 (2019-6-4 14:23):

我发现用append可以避免这一点。。。传参我看了，但是没看懂。。   
def preorder(self, node, search, path, resultpath, finish):
        if not node or finish == 1:
            return
        path.append(node.val)
        if node.val == search.val:
            finish = 1
            resultpath.append(copy.deepcopy(path))
        self.preorder(node.left, search, path, resultpath, finish)
        self.preorder(node.right, search, path, resultpath, finish)
        path.pop()

楼主你最后for循环i给丢了。。。
试着按楼主思路改了下。。。感觉改动还蛮大的，细节问题也比较多，直接贴代码好了，有些地方注释掉了看起来会比较乱……

1.     def lowestCommonAncestor(self, root, p, q):
   
2.         path = []
   
3.         # node_p_path = []
   
4.         # node_q_path = []
   
5.         # finish = 0
   
6.         node_p_path = self.preorder(root, p, path)
   
7.         path = []
   
8.         # finish = 0
   
9.         node_q_path = self.preorder(root, q, path)
   
10.         # path_len = 0
    
11.         if len(node_p_path) < len(node_q_path):
    
12.             path_len = len(node_p_path)
    
13.         else:
    
14.             path_len = len(node_q_path)
    
15.         # result = TreeNode(0)
    
16.         for i in range(path_len):
    
17.             # if node_p_path == node_q_path:
    
18.             if node_p_path[i] == node_q_path[i]:
    
19.                 result = node_p_path[i]
    
20.         # return result.val
    
21.         return result
    
22. 
    
23.     def preorder(self, node, search, path):
    
24.         # if not node or finish == 1:
    
25.         #     return
    
26.         if not node:
    
27.             return []
    
28.         # path.append(node.val)
    
29.         path.append(node)
    
30.         if node.val == search.val:
    
31.             # finish = 1
    
32.             return path
    
33.             # resultpath = copy.deepcopy(path)
    
34.             # return resultpath
    
35.         left = self.preorder(node.left, search, path)
    
36.         if left:
    
37.             return left
    
38.         # path.pop()
    
39.         right = self.preorder(node.right, search, path)
    
40.         if right:
    
41.             return right
    
42.         path.pop()

复制代码