您所在位置： &
 &  & 
出国PhD申请留学面试问题准备我的面试准备问题.doc 46页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：100 &&
你可能关注的文档：
·····
··········
我的面试准备问题
有些问题的答案不是原创的，在此向原创者致敬。有些问题的答案不便贴出来，也删掉了。红色标出来的是我被问到的问题。关于我的面试的详细情况请见：
申请情况
1.为什么选择这所学校
The program of Plant Biology attracts me. This is an intercollege program, and students can communicate with different faculty members instead of only one. They have diverse expertise so students can learn more. One of the students from our college went to PSU two years ago, she said PSU has the perfect academic atmosphere and pay high attention to international students.
2.选择小校还是大校Will you like to study in a small but with high quality university or a big university like Harvard or Princeton?
First, I will choose a university according to its research area and quality. If they are similar, I will choose a large university because a large university will provide more chances to communicate with people of different background.
3.通过什么方式知道了这所学校
I learn PSU from my elder schoolmates.
4.是否联系了其它学校或本校的其它老师
Yes, they are XXXXXXXXX
5.申请了几个学校
5.
为什么只申请了5所这么少？I think 5 is enough. Even if I applied 20 schools, and get 10 offers, I can only accept 1 offer. Also, I didn't have much time to spend on application.
8．如果有其它学校录取了你去不去
9．把本校放在第几位Where/How do you rank this university?
10．为什么选择在美国学习
See the world
11．为中美两国教育体制的不同做了那些准备What preparations do you make when you are faced with the education differences between China and USA?
12．有没有同学在此学校就读
Yes. Miss XXXX
13.如果我们给了你offer,你会来吗？七月能来吗
I am not sure now.
I only can come in August
14．如果给offer的话需要多久能答复？I’m afraid around April 15th.
15.有没有对哪个教授感兴趣Is there some special faculty you are interested in?
16．读过我的介绍吗？Yes, roughly.
17．你认为我们在哪些方面有共同的研究兴趣？
18.你对我们学校有什么期望？
19.你认为那些东西有助于申请What do you think will help to your application?
学习计划及毕业打算
1.在这个学校怎样学习What's your plan in this university.?
2.希望通过研究生学习获得什么What do you want to receive through the graduate study ?
3.设想一个特别想弄明白的学术问题，并且设计实验来解决。
4.毕业后的打算What's your plan after you finish your study? What do you plan to do in the future? future career plan
5.是否回国Wo
正在加载中，请稍后...查看: 3942|回复: 22
算法超级大总结-- 面试中二叉树中常常考的题目欢迎讨论
精华主题学分
活跃农民-感谢提供高质量信息和讨论, 积分 321, 距离下一级还需 679 积分
在线时间 小时
注册一亩三分地论坛，查看更多干货！
才可以下载或查看，没有帐号？
感谢以下文章的作者：
二叉树是面试中的常考题目。而且许多别的题是基于二叉树的，所以我们必须对二叉树
无比熟悉。
经过多日的努力，以下所有的题目主页君全部实现了一次，并且加上自己的理解，所有
的算法都基本最优化过，并且递归非递归都实现了一次。敬请大家指正：
以下是目录，以及主页君的代码
1. 求二叉树中的节点个数:
& && &&&getNodeNumRec（递归），getNodeNum（迭代）
2. 求二叉树的深度:
& && &&&getDepthRec（递归），getDepth
3. 前序遍历，中序遍历，后序遍历:
& && &&&preorderTraversalRec, preorderTraversal, inorderTraversalRec,
postorderTraversalRec
4. 分层遍历二叉树（按层次从上往下，从左往右）:
& && &&&levelTraversal, levelTraversalRec（递归解法）
5. 将二叉查找树变为有序的双向链表:
& && &&&convertBST2DLLRec, convertBST2DLL
6. 求二叉树第K层的节点个数：
& && &&&getNodeNumKthLevelRec, getNodeNumKthLevel
7. 求二叉树中叶子节点的个数：
& && &&&getNodeNumLeafRec, getNodeNumLeaf
8. 判断两棵二叉树是否相同的树：
& && &&&isSameRec, isSame
9. 判断二叉树是不是平衡二叉树：isAVLRec
10. 求二叉树的镜像（破坏和不破坏原来的树两种情况）：
& &&&mirrorRec, mirrorCopyRec
& &&&mirror, mirrorCopy
10.1 判断两个树是否互相镜像：isMirrorRec isMirror
11. 求二叉树中两个节点的最低公共祖先节点：
& && && &LAC& && &&&求解最小公共祖先, 使用list来存储path.
& && && &LCABstRec&&递归求解BST树.
& && && &LCARec& &&&递归算法 .
12. 求二叉树中节点的最大距离：
& && && &getMaxDistanceRec
13. 由前序遍历序列和中序遍历序列重建二叉树：
& && && &rebuildBinaryTreeRec
14. 判断二叉树是不是完全二叉树：
& && && &isCompleteBinaryTree, isCompleteBinaryTreeRec
15. 找出二叉树中最长连续子串(即全部往左的连续节点，或是全部往右的连续节点）
& && && &findLongest
<p id="rate_42" onmouseover="showTip(this)" tip="非常感谢&大米 + 3 升
" class="mtn mbn">
本帖被以下淘专辑推荐:
& |主题: 87, 订阅: 144
精华主题学分
在线时间 小时
虽然是参考的 但是也是有优化过，比原文章其实更优化
精华主题学分
在线时间 小时
希望大家一起来讨论
精华主题学分
在线时间 小时
希望大家一起来讨论
lz是今年入学的ini学生吗？
精华主题学分
在线时间 小时
lz是今年入学的ini学生吗？
您是？ 加我的qq 私聊吧&&我是 我已经2年级了。
精华主题学分
在线时间 小时
精华主题学分
在线时间 小时
顶一下自己。 谢谢支持
精华主题学分
在线时间 小时
精华主题学分
在线时间 小时
希望有更多的人看到本帖子。
精华主题学分
在线时间 小时
顶一下帖子。
精华主题学分
在线时间 小时
顶一下 希望更多的人可以看到。
精华主题学分
在线时间 小时
public static int getDepthRec(TreeNode root) {
& && &&&if (root == null) {
& && && && &return -1;
& && &&&return Math.max(getDepthRec(root.left), getDepthRec(root.right)) + 1;
若为null应该返回0才对吧
精华主题学分
在线时间 小时
public static int getDepthRec(TreeNode root) {
& && &&&if (root == null) {
& && && && &return -1;
标准定义是-1. 这个定义你到时与面官确认吧。
精华主题学分
在线时间 小时
public static int getDepthRec(TreeNode root) {
& && &&&if (root == null) {
& && && && &return -1;
在树的深度定义中，只有一个节点，定义depth为0.
精华主题学分
在线时间 小时
在树的深度定义中，只有一个节点，定义depth为0.
递归到了base case后停下，若最后一步返回一个-1，会比真实深度少1. 欢迎指教
精华主题学分
在线时间 小时
递归到了base case后停下，若最后一步返回一个-1，会比真实深度少1. 欢迎指教
null的真实深度就是-1.这是树的定义。你可以查一下算法书。 depth的定义是：从根到最远的叶子节点的边的长度。 如果只有一个root,长为0，如果是null,长为-1
精华主题学分
在线时间 小时
null的真实深度就是-1.这是树的定义。你可以查一下算法书。 depth的定义是：从根到最远的叶子节点的边的 ...
谢谢楼主，我发现国内的二叉树和国外的教材定义不同，root的depth的确是0. 国内的是1. 而且我发现我把depth和height也搞混了。非常感谢！
精华主题学分
在线时间 小时
null的真实深度就是-1.这是树的定义。你可以查一下算法书。 depth的定义是：从根到最远的叶子节点的边的 ...
谢谢楼主，我发现国内的二叉树和国外的教材定义不同，root的depth的确是0. 国内的是1. 而且我发现我把depth和height也搞混了。非常感谢！
精华主题学分
在线时间 小时
public static int getMaxDistanceRec(TreeNode root) {
& && &&&return getMaxDistanceRecHelp(root).maxD
& & public static Result getMaxDistanceRecHelp(TreeNode root) {
& && &&&Result ret = new Result(-1, -1);
& && &&&if (root == null) {
& && && && &
& && &&&Result left = getMaxDistanceRecHelp(root.left);
& && &&&Result right = getMaxDistanceRecHelp(root.right);
& && &&&// 深度应加1， the depth from the subtree to the root.
& && &&&ret.depth = Math.max(left.depth, right.depth) + 1;
& && &&&// 左子树，右子树与根的距离都要加1，所以通过根节点的路径为两边深度+2
& && &&&int crossLen = left.depth + right.depth + 2;
& && &&&// 求出cross根的路径，及左右子树的独立路径，这三者路径的最大值。
& && &&&ret.maxDistance = Math.max(left.maxDistance, right.maxDistance);
& && &&&ret.maxDistance = Math.max(ret.maxDistance, crossLen);
我想再问问 maxdistance 是 左右子树的max depth 和 crossLen 进行比较的最大值吗？若如此，为什么需要这个result 的结构呢
精华主题学分
在线时间 小时
谢谢楼主，我发现国内的二叉树和国外的教材定义不同，root的depth的确是0. 国内的是1. 而且我发现我把dep ...
国内写错了吧！！！ 国内经常搞这些事 自己都没弄懂还乱教学生。
<form method="post" autocomplete="off" id="fastpostform" action="forum.php?mod=post&action=reply&fid=84&tid=106872&extra=&replysubmit=yes&infloat=yes&handlekey=fastpost"
onSubmit="
// TODO Howard 11/3/2015
var sbtn = $('fastpostsubmit');
sbtn.disabled =
sbtn.innerHTML = ' 回复发表中... ';
sbtn.setAttribute('background', sbtn.style.background);
sbtn.setAttribute('bordercolor', sbtn.style.borderColor);
sbtn.style.background = '#C7C7C7';
sbtn.style.borderColor = '#8B8B8B';
var form =
// --product--
var isValid = fastpostvalidate(form, null, 0);
if(!isValid) reoverBtn();
return isV
// --product--
// --testing--
//setTimeout(function() {
// var isValid = fastpostvalidate(form, null, 0);
// if(!isValid) reoverBtn();
//}, 2000);
// --testing--
您需要登录后才可以回帖
回帖并转播
回帖后跳转到最后一页
一亩三分地推荐 /5
地主Warald亲手做你的申请，针对你的背景和目标，考虑申请、学习、就业、移民等系列问题，制定申请策略。
“offer”指全额奖学金，免学费全免+每月工资，Berkeley, CMU, JHU, UIUC, Gatech, UMich, UCLA, Columbia，欢迎观赏。
电子工程、计算机、统计、金数金工、化工等, Stanford, Berkeley, CMU, Cornell, Yale, Columbia, Chicago, Duke, UPenn, UIUC, Brown, UMich, JHU等
有留学、申请、找工、职业规划上的难题？先上论坛提问！
论坛考古也帮不上忙，发帖得到的回答仍然不够？电话找Warald来解答！
WARALD新书上市啦：《你不知道的美国留学》清华大学出版社，各大电商发售
Powered by数据结构与算法中，树一般会应用在哪些方面？为什么？- 百度派
{{ mainData.uname }}
：{{ mainData.content }}
{{ prevData.uname }}
：{{ prevData.content }}
{{ mainData.uname }}
：{{ mainData.content }}
0 || contentType !== 1" class="separate-line">
：{{ item.content }}
算法与数据结构
3">等{{ uList.length }}人邀请你回答
数据结构与算法中，树一般会应用在哪些方面？为什么？
问题说明（可选）：
扫一扫分享到微信
{{ log.sign }}
可能对你的问题感兴趣
暂无相关用户
，才能邀请用户
，才能邀请用户
你已邀请15人，不可再邀请
抽象地说，基本上有序列的地方就可以应用树，因为树结构即是一种序列索引结构。（我在这里提到的序列是一个广义的概念，一堆东西排在一起就叫序列。）DOM, AST 等应用都是对人脑分层分类认知的建模, 都是树...
抽象地说，基本上有序列的地方就可以应用树，因为树结构即是一种序列索引结构。（我在这里提到的序列是一个广义的概念，一堆东西排在一起就叫序列。）DOM, AST 等应用都是对人脑分层分类认知的建模, 都是树树的一个大类是自平衡二叉搜索树 (self-balanced BST), 变种特别多:RB 树是每个节点是红色或者黑色, 颜色隔代遗传AVL 树是每个节点包含平衡因子, 等于左高-右高Splay 树是每个节点带个父节点的指针Treap 是每个节点都带个随机的 priority number, parent priority &= child priority... (其实说白了都是为了方便平衡操作给节点附加一个字段)自平衡二叉搜索树在面试中经常出现, 但做网页的互联网码农却很少用得上... 如果是当 Map 用, 往往还不如直接上哈希表. 如果是当排序用, 不如直接用排序算法... 不过也有有用的时候, 例如查找一个数字的上下界.树的另一个大类是 Trie, 特点是能保证字典序, 存储词典的空间压缩率高, 能做前缀搜索. 在正则匹配, 数据压缩, 构建索引都可能用到. Trie 也有不少变种:Double Array - trie 的一个经典实现 (这实现其实不算树, 也不适合处理非 ascii 字符的情况)Patricia Trie (Radix-Tree) - 每个节点可以存一段字符串而不限于一个字符Judy Array - 基于 256-ary radix tree, 用了 20 种压缩方式, 极其复杂...Burst Trie - 如果一个子树足够小, 就用 binary 堆的方式存储, 不过压缩效果一般HAT Trie - 压缩率高而且不容易出现 CPU cache miss, 查速接近哈希表而耗内存少得多. 节点可以是以下三种之一: Array Hash, 序列化的 Bucket, 传统 Trie nodeMARISA Trie - 压缩率最高, 支持 mmap 载入, 也是用了很多压缩技巧的复杂实现, 就是构建比较花时间, 也不能动态更新Clojure 是伴随着不少 persistent (immutable) data structure 而出现的, 尤其是考虑到 Immutable 的数据结构的时候, 树好像就变成了你的唯一选择... immutable 的树也是天生方便并行操作的.HAMT 的技巧是利用 CPU 指令 popcnt 做快速的小表查询, 实现了 immutable 哈希表/动态数组RRB tree 实现了 immutable 的动态数组, 实现更复杂一点, 去掉了 n-way 的限制总之，当我们看到一个树形数据结构，主要应该考察以上两个方面：①它是如何建立索引的？②它是如何维持稳定的？
扫一扫分享到微信
，为自己喜欢的生活而活
数据结构的算法，并没有多少种算法，关于树，其实都是对DOM, AST 等应用，对人脑分层分类认知的建模,。树的一个大类是自平衡二叉搜索树 (self-balanced BST), 变种特别多:RB 树是每个节点是红色或者黑色...
& & & 数据结构的算法，并没有多少种算法，关于树，其实都是对DOM, AST 等应用，对人脑分层分类认知的建模,。树的一个大类是自平衡二叉搜索树 (self-balanced BST), 变种特别多:RB 树是每个节点是红色或者黑色, 颜色隔代遗传AVL 树是每个节点包含平衡因子, 等于左高-右高Splay 树是每个节点带个父节点的指针& & & & Treap 是每个节点都带个随机的 priority number, parent priority &= child priority&Double Array - trie 的一个经典实现 (这实现其实不算树, 也不适合处理非 ascii 字符的情况)&Patricia Trie (Radix-Tree) - 每个节点可以存一段字符串而不限于一个字符。Judy Array - 基于&256-ary radix tree, 用了 20 种压缩方式, 极其复杂...Burst Trie - 如果一个子树足够小, 就用&binary 堆的方式存储, 不过压缩效果一般。& & &HAT Trie - 压缩率高而且不容易出现 CPU cache miss, 查速接近哈希表而耗内存少得多. 节点可以是以下三种之一: Array Hash, 序列化的 Bucket, 传统 Trie node。& & & MARISA Trie - 压缩率最高, 支持 mmap 载入, 也是用了很多压缩技巧的复杂实现, 就是构建比较花时间, 也不能动态更新。& & & 总的来说，只要有序列的地方就可以应用树，因为树结构即是一种序列索引结构。序列的核心接口就是三个cha：插、查、X。
扫一扫分享到微信
数据结构与算法中，树一般会应用在哪些方面？为什么？
，才能进行回答
一个问题只能回答一次，请 点击此处 查看你的答案
3人关注了此问题面试题集-树和图
这类问题主要有以下两种形式：
1、 完成创建一个树/查找一个结点/删除一个结点/其他常见的算法
2、 完成对一个已知算法的修改
不管怎样，我们强烈推荐你在面试之前搞懂与树有关的重要算法。如果你对树非常熟悉，那么就可以轻松应对一些棘手的问题了。我们给出一些非常重要的几点：&
重要提示：并非所有的二叉树都是二叉查找树当被问到有关二叉树的时候，许多面试者自以为面试官是指二叉查找树，而面试官实际上是说二叉树。所以，认真听是否有&查找&那个词。如果你没有听到，那么面试官可能就是指那些没有经过特定排序的结点的二叉树。如果你不确定，那就问下吧。
有关二叉树的最基础算法
在你面试之前你应该熟知以下算法：
1、中序遍历：首先访问左结点，接着访问根结点，然后访问右结点（通常在二叉查找树中使用）。
2、先序遍历：首先访问根节点，接着访问根节点的左子节点下的子树内的节点，然后访问根节点的右子节点下的子树内的节点。
3、后序遍历：首先访问根节点，接着访问根节点的右子节点下的子树内的节点，然后访问根节点的左子节点下的子树内的节点。
4、插入结点：在二叉查找树中，我们插入一个变量v的方法是这样的。跟根节点比较，如果v大于root，那么去右边，否则去左边。我们重复这样的比较直到有一个空结点。
注意：调整或者删除查找树的问题很少会问到，但你应该知道他们是如何工作的。这有助于你从其他面试者区分出来。&&
有关图遍历的最基础算法
在你面试之前你应该熟知以下算法：
1、深度优先搜索DFS（Depth&First&Search）：DFS算法涉及在访问兄弟结点前先访问自身以及子结点。
2、广度优先搜索BFS（Broad&First&Search）：&BFS算法涉及在访问子结点前先访问自身以及兄弟结点。&
4.1完成一个用来判断一颗树是否是平衡树的函数。这个问题的目的是，平衡树是指两个叶结点在距离根结点的距离上不会超过1。pg123
思路很简单：最小深度与最大深度的差别是不超过1.因此最大与最小深度的差值就是树中最大的深度差值。
4.2对于一个有方向的图，设计一种算法用来判断在两个顶点之间是否有路径。pg124思路很简单：最小深度与最大深度的差别是不超过1.因此最大与最小深度的差值就是树中最大的深度差值。
这个问题通过对图的遍历就可以轻松解决，比如深度优先搜索或者广度优先搜索。我们从其中一个结点开始遍历，遍历过程中检查另外一个结点是否被找到。我们应该对算法中遍历过的结点进行标记，以避免对结点的重复访问以及循环访问。
4.3对于一个升序排列的数组，给出创建最小高度二叉树的算法。pg125
如果可能，我们尝试建立这样一个二叉树，对于每一个结点，他左分支的结点总数与右分支的结点总数一致。
算法如下：
1、插入数组中的中间数
2、将中间数左边的元素插入到左分支
3、将中间数右边的元素插入到右分支
4.4对于一个二叉查找树，设计可以给出在任一深度所有结点的链表的算法（比如树的深度是D，就有D个链接。）pg126
我们可以做对树一层层的遍历，对树的初次遍历可以做轻微的修改。
在常见的初次遍历中，我们在遍历结点的时候不关心现在所在的层。在这个问题中，就有必要知道当前的层信息。因此我们使用一个虚拟结点来预测我们是否完成了本层并进行下一层访问。
4.5对于一个每一个结点都有一个指向其父结点的二叉查找树，设计一个寻找给定结点下一个结点的算法。pg127
解决这个问题，我们需要仔细思考中序遍历中到底发生了什么。在先序遍历中，我们访问X.left,X,然后是X.right.
因此，如果我们想找到X.successor(),我们这样解决：
1、如果X有右分支，那么所谓的继承者肯定在X的右侧。很明确，在树的那个分支上，需要首先访问最左边的子结点。
2、否则我们访问X的父结点（记做P）
a) 如果X有一个左子结点（P.left=X），那么P就是X的继承者。
b) 如果X有一个右子结点（P.right=X），因此我们就调用successor(P)。
4.6设计一个二叉树中两个结点的第一个共同祖先结点的算法，并给出代码。避免在数据结构中存储额外的结点。注意：这不一定需要是二叉查找树。pg128
假设这是二叉查找树，我们可以在这两个结点上做一个改进的搜索来看这两路径在哪里分叉。可惜的是，这不是二叉查找树，因此我们得试其他思路。
如果每个结点都连接到他的父结点，那么我们就可以跟踪p跟q的路径直到他们交叉。
另外，你可以看一个p跟q都在同一侧的一个分割线。也就是说，如果p跟q都在结点的左侧，那就在左侧分支中去寻找共同的祖先。当p跟q不在同一侧的时候，你不得另想其他办法。
对于任意一个结点r，我们有以下：
1、如果p在一侧，q在另外一侧，那么r就是最近的共同的祖先。
2、否则的话，最近的共同的祖先就在左侧或者右侧。
因此，我们可以给出一个叫左搜索-右搜索的递归算法来计算当前结点的左侧跟右侧分别有多少个结点（p或者q）。如果在某一侧只有2个结点，那么我们就需要判断这个子结点是不是p或者q（因为这种情况下，当前结点就是最近的共同的祖先）。如果不是p或者q，那我们就得从子结点开始继续搜索。
如果需要寻找的结点（p或者q）在当前结点的右侧，此外另一个结点在另一侧。那么当前及诶点就是最近的共同的祖先。
4.7如果有两个巨大的树，T1、T2，其中前者有百万个结点，后者有几百个结点。设计一种算法判断T2是否是T1的一个分支。pg130
注意问题的特别指出T1有百万个结点，也就是说我们应该特别注意空间的开支。举个例子，如果T1有1000万个结点，那么单单数据量就是大约40mb。我们可以创建一个字符串来表示中序跟先序的遍历。如果T2的先序遍历是T1先序遍历的一个分支，T2的中序遍历是T1中序遍历的一个分支，那么T2就是T1的第一分支。我们可以通过使用一个后缀树来确认。然而，我们可能会受到内存的限制，因为后缀树对于内存是极端敏感的。如果这个成了一个问题，那么我们就得试下另外一个思路。
其他思路：treeMatch程序访问T2的每个结点最多一次，对于T1的每个结点的访问次数不超过1。最极端的情况是O(m*n)，n跟m分别表示T1跟T2的大小。如果k表示T2的根节点在T1中出现的次数，那么极端的时间复杂度是O(k*m+n)。
4.8对于一个任何结点都包含值的二叉树，设计一种算法实现打印出和是那个值的所有路径。注意可以是任何路径（不需要一定从根结点开始）。pg131
解答undefined
我们通过简化这个问题来求解。假设这个路径从根结点开始会怎样？这样的话，我们就得到一个更简单的问题了：undefined
从根节点开始，然后左分支跟右分支，计算每个路径的总数。当我们找到这个总和的时候，我们就打印出当前路径。注意我们直到找到这个总和才停止计算。为什么？因为我们可以遇到下面这种情况（假设我们找总和是5的路径）：2 + 3 + &4 + 3 + 1 + 2。如果我们遇到2+3就停止计算，我们就可以错过其他一些路径（2 + 3 + -4 + 3 + 1 和3 + -4 + 3 + 1 + 2）。因此我们对于每个可能的路径都要试一次。undefined
好，现在假设这个路径可以从任何一个结点开始？ 在这种情况下，我们做个小修改。在每个结点，我们核对下是否找到总和。这并不是指我们是否从一个有这个总和的路径开始，而是这个路径达到总和了吗？undefined
这个算法的时间复杂度如何呢？假设一个在第r层的结点，我们做r数量级的计算。我们猜测是O(nlgn)，或者我们仔细算下：第r层有2^r个结点类似的逻辑，空间复杂度是O(nlgn)。
看过本文的人也看了：
我要留言技术领域：
取消收藏确定要取消收藏吗？
删除图谱提示你保存在该图谱下的知识内容也会被删除，建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗？
删除节点提示无法删除该知识节点，因该节点下仍保存有相关知识内容！
删除节点提示你确定要删除该知识节点吗？
