FB 昂赛跪经

Kyaaaaan 发表于 2017-10-13 09:12
所有最深节点可能是一个爸爸一个儿子么。。。

我这个问题是问LCA的定义，如果出现我说的那种情况，返回爷爷还是爸爸，不知道你那个面试官是哪种定义

Kyaaaaan 发表于 2017-10-13 09:12
所有最深节点可能是一个爸爸一个儿子么。。。

针对题目的话，如果最深的只有一个，返回那一个叶结点还是最深叶结点的爸爸

多叉树所有最深节点的LCA

我来说一个思路，先traverse一遍, 把每一个点的深度和父亲存在hash表里面，然后把最深得那些点放在queue里面做个向父亲节点的bfs，队列的size会不断变小，当只有一个点的时候就是答案啦。

GardenAAA 发表于 2017-10-13 09:53
针对题目的话，如果最深的只有一个，返回那一个叶结点还是最深叶结点的爸爸

哦哦我这里是较低的那个

Kyaaaaan 发表于 2017-10-13 09:05
口述。。。。。

那signature 什么的也要自己写在白板上吗？

zoe112233 发表于 2017-10-13 12:00
那signature 什么的也要自己写在白板上吗？

signature是啥。。

补一个递归的多叉树的做法，建立一个returnType，来记录lca和depth
如果root的子树的returnType中有两个相等的最大值，那么返回root, depth+1
如果root的子树的return Type中只有一个最大值，返回该最大值对应的lca, depth+1

楼主你的题好常规～～

Kyaaaaan 发表于 2017-10-13 12:03
signature是啥。。

就比如
public boolean isValidBST(TreeNode root) {
}

这个会像leetcode一样给吗？

zoe112233 发表于 2017-10-13 13:56
就比如
public boolean isValidBST(TreeNode root) {
}

恩他给好