l***u
发帖数: 26081 | 1 贡献一道MS面试题
输入：
一棵二叉树和树上的一个结点（每个节点有一个整形数据）
输出：
这棵树上的另一个节点（如果不存在返回NULL），要求这个节点的整形数据与给定节点的差距最小（如
果有多个这样的节点就返回与给定节点的树距离[1]最小的任意一个）
注：
1. 树距离定义为f(x,y)=L(x)-L(c)+L(y)-L(c)，其中L是某节点的层数，c是x和y的最小公共祖
先节点 |
c****p
发帖数: 6474 | 2 二叉树是BST么
点的差距最小（如
最小公共祖
【在 l***u 的大作中提到】
: 贡献一道MS面试题
: 输入：
: 一棵二叉树和树上的一个结点（每个节点有一个整形数据）
: 输出：
: 这棵树上的另一个节点（如果不存在返回NULL），要求这个节点的整形数据与给定节点的差距最小（如
: 果有多个这样的节点就返回与给定节点的树距离[1]最小的任意一个）
: 注：
: 1. 树距离定义为f(x,y)=L(x)-L(c)+L(y)-L(c)，其中L是某节点的层数，c是x和y的最小公共祖
: 先节点
|
l***u
发帖数: 26081 | 3 不是二叉搜索树，换句话说，至少要遍历树上的每个节点
【在 c****p 的大作中提到】
: 二叉树是BST么
:
: 点的差距最小（如
: 最小公共祖
|
m**q
发帖数: 189 | 4 这个好像直接做就行了
pre-order遍历，在每一个节点判断一下本节点值和给定值的差距，
小于当前的最小差值则更新
为了处理多个最小差值的情况，先遍历一次把从root到给定节点的
路径上的所有节点存到vector里面，同时计算出最小的差值是多少。
然后pre-order遍历，同时记录root到当前节点的路径，在每个节点
判断一下差值，如果等于最小差值，则计算距离是否小于当前的
最小距离，如果小于则更新。
预期复杂度O(n),最坏复杂度O(nlgn)，对应于每个节点都要查找路径
的情况
点的差距最小（如
最小公共祖
【在 l***u 的大作中提到】
: 贡献一道MS面试题
: 输入：
: 一棵二叉树和树上的一个结点（每个节点有一个整形数据）
: 输出：
: 这棵树上的另一个节点（如果不存在返回NULL），要求这个节点的整形数据与给定节点的差距最小（如
: 果有多个这样的节点就返回与给定节点的树距离[1]最小的任意一个）
: 注：
: 1. 树距离定义为f(x,y)=L(x)-L(c)+L(y)-L(c)，其中L是某节点的层数，c是x和y的最小公共祖
: 先节点
|
