门冲电面compare tree diff

楼主，follow up是什么啊？

phmhmt2016 发表于 2021-7-23 05:57
这是个好问题，要问面试官，答案是key是唯一的

多谢回答！再请问一个问题，我看有的帖子说这题要分开存新增，删除更新节点，不知道你面试时要求只是个数还是说要返回好几个list呢？谢谢！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

匿名者 发表于 2021-7-19 20:46
你說得對, 已經修正了, 看看還有沒有問題
過幾天我也要phone interview了, 希望不會被問到這道, 太複雜 ...

楼主 line51 错了吧，因为value扁了的话只是算是modify了一个node。所以应该是1，不是2

A very succinct solution using Python (please add rice if you like it !!!)

1. class TreeNode(object):
   
2. 
   
3.     def __init__(self, key, value):
   
4.         self.key = key  # this should be unique; int
   
5.         self.value = value # int
   
6.         self.children = [] # list of TreeNodes
   
7.         
   
8. class Solution(object):
   
9. 
   
10.     def countNodes(self, node):
    
11.         if node is None:
    
12.             return 0
    
13. 
    
14.         count = 1
    
15.         
    
16.         for child in node.children:
    
17.             count += self.countNodes(child)
    
18.        
    
19.         return count
    
20. 
    
21.     def findDiffNodes(self, root1, root2):
    
22.         
    
23.         if root1 is None and root2 is None:
    
24.             return 0
    
25.         
    
26.         if root1 is None or root2 is None or root1.key != root2.key:
    
27.             return self.countNodes(root1) + self.countNodes(root2)
    
28.         
    
29.         diffCount = 0
    
30.         
    
31.         if root1.value != root2.value:
    
32.             diffCount += 2
    
33.             
    
34.         childsMap1 = { child.key: child for child in root1.children }
    
35.         childsMap2 = { child.key: child for child in root2.children }
    
36.         
    
37.         childsAllKeys = set(childsMap1.keys()).union(set(childsMap2.keys()))
    
38.         
    
39.         for childKey in childsAllKeys:
    
40.             diffCount += self.findDiffNodes(childsMap1.get(childKey), childsMap2.get(childKey))
    
41.             
    
42.         return diffCount

复制代码

匿名者 发表于 2021-7-19 19:46
你說得對, 已經修正了, 看看還有沒有問題
過幾天我也要phone interview了, 希望不會被問到這道, 太複雜 ...

为什么 node1.val != node2.val 要diff=2，改变val不是应该算一个diff吗