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

李冬冬 发表于 2019/06/04 14:24:33


还是没用啊，求教   
def preorder(self, node, search, path, resultpath, finish):
        if not node or ...

额……这次改的怎么感觉又绕回来了……而且preorder返回的东西还是没人接收并继续返回出去呀……另外不光preorder，外面的部分细节也有错误改了没，比如最后的for循环里我记得少了i……
我发现我发的代码被审核了没发出来……

补充内容 (2019-6-4 15:09):
建议楼主再好好单步调试一下…更容易看出很多问题

Jarvet 发表于 2019-6-4 15:06
额……这次改的怎么感觉又绕回来了……而且preorder返回的东西还是没人接收并继续返回出去呀……另外不光 ...

import copy
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        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
        node_p_path=copy.deepcopy(node_p_path[0])
        node_q_path=copy.deepcopy(node_q_path[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

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

Jarvet 发表于 2019-6-4 15:06
额……这次改的怎么感觉又绕回来了……而且preorder返回的东西还是没人接收并继续返回出去呀……另外不光 ...

在pycharm运行没问题，在leetcode里运行说AttributeError: 'int' object has no attribute 'val'

append是将整个path数组作为一个元素添加到result中，可以用（而且是O(1)操作效率高..）但按照楼主原来的思路应该是用extend来in-place拷贝数组：https://docs.python.org/3/tutorial/datastructures.html

此外返回结果类型是TreeNode，path里也要存TreeNode，所以还有两行代码要修改一下就可以accept（数组下标i那个应该是楼主发帖时被吞掉了，从斜体代码可以看出来）：

1. class Solution:
   
2.     def lowestCommonAncestor(self, root, p, q):
   
3.         path = []
   
4.         node_p_path = []
   
5.         node_q_path = []
   
6.         finish = 0
   
7.         self.preorder(root, p, path, node_p_path, finish)
   
8.         path = []
   
9.         finish = 0
   
10.         self.preorder(root, q, path, node_q_path, finish)
    
11.         path_len = 0
    
12.         if len(node_p_path) < len(node_q_path):
    
13.             path_len = len(node_p_path)
    
14.         else:
    
15.             path_len = len(node_q_path)
    
16.         result = root
    
17.         for i in range(path_len):
    
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, result, finish):
    
24.         if not node or finish == 1:
    
25.             return
    
26.         # path.append(node.val)
    
27.         path.append(node)
    
28.         if node.val == search.val:
    
29.             finish = 1
    
30.             # result = copy.deepcopy(path)
    
31.             result.extend(path)
    
32.         self.preorder(node.left, search, path, result, finish)
    
33.         self.preorder(node.right, search, path, result, finish)
    
34.         path.pop()

复制代码

magicsets 发表于 2019-6-4 15:50
append是将整个path数组作为一个元素添加到result中，可以用（而且是O(1)操作效率高..）但按照楼主原来的思 ...

谢谢，我已经懂了

magicsets 发表于 2019-6-4 15:50
append是将整个path数组作为一个元素添加到result中，可以用（而且是O(1)操作效率高..）但按照楼主原来的思 ...

其实我想进行赋值操作的，result=path，把path直接赋值给result，但是我这样写会报错，我也不知道为啥，所以用copy.deepcopy或者append了

如果想要理解原理的话可以仔细看一下这个slides第2页到第8页开始关于"pass by value"和"pass by reference"的介绍：
https://ppawar.github.io/CSE216-S19/slides/PDF/Python3-SBU.pdf

更深入一点的话可以看这个关于Python内存模型的slides：
https://www.cs.cornell.edu/cours ... presentation-10.pdf