门冲电面compare tree diff

倒序浏览 · 2021-7-17 14:31:33

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由匿名于 2021-7-17 02:33 编辑

经典面经题目，面试官结束的时候还夸了一波第一次见到有人一次写对的。面过之后三小时通知进入下一轮。

题目：给定两个n叉树，求这两个树之间有多少个节点差异。

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

附上鄙人的一个解法

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

希望帮到的看官加加米。

匿名用户-7O50L *2021-7-20 11:46:41* · 2021-7-20 11:46:41

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

niubuzhi · 2021-10-25 09:45:11

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

class TreeNode(object):
def __init__(self, key, value):
self.key = key # this should be unique; int
self.value = value # int
self.children = [] # list of TreeNodes
class Solution(object):
def countNodes(self, node):
if node is None:
return 0
count = 1
for child in node.children:
count += self.countNodes(child)
return count
def findDiffNodes(self, root1, root2):
if root1 is None and root2 is None:
return 0
if root1 is None or root2 is None or root1.key != root2.key:
return self.countNodes(root1) + self.countNodes(root2)
diffCount = 0
if root1.value != root2.value:
diffCount += 2
childsMap1 = { child.key: child for child in root1.children }
childsMap2 = { child.key: child for child in root2.children }
childsAllKeys = set(childsMap1.keys()).union(set(childsMap2.keys()))
for childKey in childsAllKeys:
diffCount += self.findDiffNodes(childsMap1.get(childKey), childsMap2.get(childKey))
return diffCount

复制代码

匿名用户-7O50L *2021-7-19 06:28:25* · 2021-7-19 06:28:25

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

匿名用户-OXRJH *2021-7-18 03:04:40* · 2021-7-18 03:04:40

楼主也是看了面经才过的吧？

左飞机626

楼主你要的查看积分能稍微低点吗？帮你加米

lifengyi

这题的follow up可以做的相当有难度

phmhmt2016

匿名用户发表于 2021-07-18 15:28:25
我也不夠分看答案, 但根自己對題目和要求的理解寫了以下的code

class TreeNode {

今天也碰到这题了，层主的解法有个问题。不能用sort，而是要转成hashmap找相同的key。比如abc和bc，单纯sort比的不对

taoyuanming886

phmhmt2016 发表于 2021-7-19 20:19
今天也碰到这题了，层主的解法有个问题。不能用sort，而是要转成hashmap找相同的key。比如abc和bc，单纯so ...

请问children里如果多个node有相同的key怎么办呢？普通使用hashmap的话不好做呀。。

phmhmt2016

taoyuanming886 发表于 2021-07-22 22:42:25
请问children里如果多个node有相同的key怎么办呢？普通使用hashmap的话不好做呀。。

这是个好问题，要问面试官，答案是key是唯一的

yanzhufanchen

phmhmt2016 发表于 2021-7-19 20:19
今天也碰到这题了，层主的解法有个问题。不能用sort，而是要转成hashmap找相同的key。比如abc和bc，单纯so ...

sort完之后用类似merge sort的two pointer办法就可以了吧