在 SegmentFault，解决技术问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。
一线的工程师、著名开源项目的作者们，都在这里：
获取验证码
已有账号？
问题对人有帮助，内容完整，我也想知道答案
问题没有实际价值，缺少关键内容，没有改进余地
原题：The radius of a tree is the maximum distance from the root to a leaf. Given a connected, undirected graph, write a procedure to find a spanning tree of minimum radius.(Hint: use breadth-first search)
思路？？？
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
提示：用广度优先算法（基本可以保证生成的树有minimum radius）
基本上就是广度优先遍历这张图，然后把遍历过的节点放到树上，并且标记下来，下次不要再访问遍历过的节点。可以考虑用个链表来储存访问过的节点。
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
可以先阅读wikipedia上关于BFS和DFS的解释以及相关的实现。
从根节点开始，每次找到最近的且没有访问过的节点。下次从所有这些节点开始，继续重复上述过程。
最小生成树也可以参考MST的相关算法，prim，kruskal（不知道有没有拼写错误）。
经典问题多看看，这种相类似的问题就会迎刃而解。
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
BFS跑一遍不就是一个最小半径生成树了么？使用邻接表存图吧.vector&int&g[SIZE].还有最小生成树（一般指的是value最小）
同步到新浪微博
分享到微博？
关闭理由：
删除理由：
忽略理由：
推广（招聘、广告、SEO 等）方面的内容
与已有问题重复（请编辑该提问指向已有相同问题）
答非所问，不符合答题要求
宜作评论而非答案
带有人身攻击、辱骂、仇恨等违反条款的内容
无法获得确切结果的问题
非开发直接相关的问题
非技术提问的讨论型问题
其他原因（请补充说明）
我要该，理由是：服务不可用。一篇文章搞定面试中的二叉树题目(java实现) - 简书
一篇文章搞定面试中的二叉树题目(java实现)
最近总结了一些数据结构和算法相关的题目，这是第一篇文章，关于二叉树的。先上二叉树的数据结构：
class TreeNode{
二叉树的题目普遍可以用递归和迭代的方式来解
1.求二叉树的最大深度
int maxDeath(TreeNode node){
if(node==null){
int left = maxDeath(node.left);
int right = maxDeath(node.right);
return Math.max(left,right) + 1;
2.求二叉树的最小深度
int getMinDepth(TreeNode root){
if(root == null){
return getMin(root);
int getMin(TreeNode root){
if(root == null){
return Integer.MAX_VALUE;
if(root.left == null&&root.right == null){
return Math.min(getMin(root.left),getMin(root.right)) + 1;
3,求二叉树中节点的个数
int numOfTreeNode(TreeNode root){
if(root == null){
int left = numOfTreeNode(root.left);
int right = numOfTreeNode(root.right);
return left + right + 1;
4,求二叉树中叶子节点的个数
int numsOfNoChildNode(TreeNode root){
if(root == null){
if(root.left==null&&root.right==null){
return numsOfNodeTreeNode(root.left)+numsOfNodeTreeNode(root.right);
5.求二叉树中第k层节点的个数
int numsOfkLevelTreeNode(TreeNode root,int k){
if(root == null||k&1){
int numsLeft = numsOfkLevelTreeNode(root.left,k-1);
int numsRight = numsOfkLevelTreeNode(root.right,k-1);
return numsLeft + numsR
6.判断二叉树是否是平衡二叉树
boolean isBalanced(TreeNode node){
return maxDeath2(node)!=-1;
int maxDeath2(TreeNode node){
if(node == null){
int left = maxDeath2(node.left);
int right = maxDeath2(node.right);
if(left==-1||right==-1||Math.abs(left-right)&1){
return -1;
return Math.max(left, right) + 1;
7.判断二叉树是否是完全二叉树
什么是完全二叉树呢？
boolean isCompleteTreeNode(TreeNode root){
if(root == null){
Queue&TreeNode& queue = new LinkedList&TreeNode&();
queue.add(root);
boolean result =
boolean hasNoChild =
while(!queue.isEmpty()){
TreeNode current = queue.remove();
if(hasNoChild){
if(current.left!=null||current.right!=null){
if(current.left!=null&&current.right!=null){
queue.add(current.left);
queue.add(current.right);
}else if(current.left!=null&&current.right==null){
queue.add(current.left);
hasNoChild =
}else if(current.left==null&&current.right!=null){
hasNoChild =
8.两个二叉树是否完全相同
boolean isSameTreeNode(TreeNode t1,TreeNode t2){
if(t1==null&&t2==null){
else if(t1==null||t2==null){
if(t1.val != t2.val){
boolean left = isSameTreeNode(t1.left,t2.left);
boolean right = isSameTreeNode(t1.right,t2.right);
return left&&
9.两个二叉树是否互为镜像
boolean isMirror(TreeNode t1,TreeNode t2){
if(t1==null&&t2==null){
if(t1==null||t2==null){
if(t1.val != t2.val){
return isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);
10.翻转二叉树or镜像二叉树
TreeNode mirrorTreeNode(TreeNode root){
if(root == null){
TreeNode left = mirrorTreeNode(root.left);
TreeNode right = mirrorTreeNode(root.right);
root.left =
root.right =
11.求两个二叉树的最低公共祖先节点
TreeNode getLastCommonParent(TreeNode root,TreeNode t1,TreeNode t2){
if(findNode(root.left,t1)){
if(findNode(root.right,t2)){
return getLastCommonParent(root.left,t1,t2);
if(findNode(root.left,t2)){
return getLastCommonParent(root.right,t1,t2)
// 查找节点node是否在当前 二叉树中
boolean findNode(TreeNode root,TreeNode node){
if(root == null || node == null){
if(root == node){
boolean found = findNode(root.left,node);
if(!found){
found = findNode(root.right,node);
12.二叉树的前序遍历
ArrayList&Integer& preOrder(TreeNode root){
Stack&TreeNode& stack = new Stack&TreeNode&();
ArrayList&Integer& list = new ArrayList&Integer&();
if(root == null){
stack.push(root);
while(!stack.empty()){
TreeNode node = stack.pop();
list.add(node.val);
if(node.right!=null){
stack.push(node.right);
if(node.left != null){
stack.push(node.left);
ArrayList&Integer& preOrderReverse(TreeNode root){
ArrayList&Integer& result = new ArrayList&Integer&();
preOrder2(root,result);
void preOrder2(TreeNode root,ArrayList&Integer& result){
if(root == null){
result.add(root.val);
preOrder2(root.left,result);
preOrder2(root.right,result);
13.二叉树的中序遍历
ArrayList&Integer& inOrder(TreeNode root){
ArrayList&Integer& list = new ArrayList&&Integer&();
Stack&TreeNode& stack = new Stack&TreeNode&();
TreeNode current =
while(current != null|| !stack.empty()){
while(current != null){
stack.add(current);
current = current.
current = stack.peek();
stack.pop();
list.add(current.val);
current = current.
14.二叉树的后序遍历
ArrayList&Integer& postOrder(TreeNode root){
ArrayList&Integer& list = new ArrayList&Integer&();
if(root == null){
list.addAll(postOrder(root.left));
list.addAll(postOrder(root.right));
list.add(root.val);
15.前序遍历和后序遍历构造二叉树
TreeNode buildTreeNode(int[] preorder,int[] inorder){
if(preorder.length!=inorder.length){
return myBuildTree(inorder,0,inorder.length-1,preorder,0,preorder.length-1);
TreeNode myBuildTree(int[] inorder,int instart,int inend,int[] preorder,int prestart,int preend){
if(instart&inend){
TreeNode root = new TreeNode(preorder[prestart]);
int position = findPosition(inorder,instart,inend,preorder[start]);
root.left = myBuildTree(inorder,instart,position-1,preorder,prestart+1,prestart+position-instart);
root.right = myBuildTree(inorder,position+1,inend,preorder,position-inend+preend+1,preend);
int findPosition(int[] arr,int start,int end,int key){
for(i =i&=i++){
if(arr[i] == key){
return -1;
16.在二叉树中插入节点
TreeNode insertNode(TreeNode root,TreeNode node){
if(root == node){
TreeNode tmp = new TreeNode();
TreeNode last =
while(tmp!=null){
if(tmp.val&node.val){
tmp = tmp.
tmp = tmp.
if(last!=null){
if(last.val&node.val){
last.left =
last.right =
17.输入一个二叉树和一个整数，打印出二叉树中节点值的和等于输入整数所有的路径
void findPath(TreeNode r,int i){
if(root == null){
Stack&Integer& stack = new Stack&Integer&();
int currentSum = 0;
findPath(r, i, stack, currentSum);
void findPath(TreeNode r,int i,Stack&Integer& stack,int currentSum){
currentSum+=r.
stack.push(r.val);
if(r.left==null&&r.right==null){
if(currentSum==i){
for(int path:stack){
System.out.println(path);
if(r.left!=null){
findPath(r.left, i, stack, currentSum);
if(r.right!=null){
findPath(r.right, i, stack, currentSum);
stack.pop();
18.二叉树的搜索区间
给定两个值 k1 和 k2（k1 & k2）和一个二叉查找树的根节点。找到树中所有值在 k1 到 k2 范围内的节点。即打印所有x (k1 &= x &= k2) 其中 x 是二叉查找树的中的节点值。返回所有升序的节点值。
ArrayList&Integer&
ArrayList&Integer& searchRange(TreeNode root,int k1,int k2){
result = new ArrayList&Integer&();
searchHelper(root,k1,k2);
void searchHelper(TreeNode root,int k1,int k2){
if(root == null){
if(root.val&k1){
searchHelper(root.left,k1,k2);
if(root.val&=k1&&root.val&=k2){
result.add(root.val);
if(root.val&k2){
searchHelper(root.right,k1,k2);
19.二叉树的层次遍历
ArrayList&ArrayList&Integer&& levelOrder(TreeNode root){
ArrayList&ArrayList&Integer&& result = new ArrayList&ArrayList&Integer&&();
if(root == null){
Queue&TreeNode& queue = new LinkedList&TreeNode&();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
ArrayList&&Integer& level = new ArrayList&Integer&():
for(int i = 0;i &i++){
TreeNode node = queue.poll();
level.add(node.val);
if(node.left != null){
queue.offer(node.left);
if(node.right != null){
queue.offer(node.right);
result.add(Level);
20.二叉树内两个节点的最长距离
二叉树中两个节点的最长距离可能有三种情况：1.左子树的最大深度+右子树的最大深度为二叉树的最长距离2.左子树中的最长距离即为二叉树的最长距离3.右子树种的最长距离即为二叉树的最长距离因此，递归求解即可
private static class Result{
public Result() {
public Result(int maxDistance, int maxDepth) {
this.maxDistance = maxD
this.maxDepth = maxD
int getMaxDistance(TreeNode root){
return getMaxDistanceResult(root).maxD
Result getMaxDistanceResult(TreeNode root){
if(root == null){
Result empty = new Result(0,-1);
Result lmd = getMaxDistanceResult(root.left);
Result rmd = getMaxDistanceResult(root.right);
Result result = new Result();
result.maxDepth = Math.max(lmd.maxDepth,rmd.maxDepth) + 1;
result.maxDistance = Math.max(lmd.maxDepth + rmd.maxDepth,Math.max(lmd.maxDistance,rmd.maxDistance));
21.不同的二叉树
给出 n，问由 1...n 为节点组成的不同的二叉查找树有多少种？
int numTrees(int n ){
int[] counts = new int[n+2];
counts[0] = 1;
counts[1] = 1;
for(int i = 2;i&=n;i++){
for(int j = 0;j&i;j++){
counts[i] += counts[j] * counts[i-j-1];
return counts[n];
22.判断二叉树是否是合法的二叉查找树(BST)
一棵BST定义为：节点的左子树中的值要严格小于该节点的值。节点的右子树中的值要严格大于该节点的值。左右子树也必须是二叉查找树。一个节点的树也是二叉查找树。
public int lastVal = Integer.MAX_VALUE;
public boolean firstNode =
public boolean isValidBST(TreeNode root) {
// write your code here
if(root==null){
if(!isValidBST(root.left)){
if(!firstNode&&lastVal &= root.val){
firstNode =
lastVal = root.
if (!isValidBST(root.right)) {
深刻的理解这些题的解法思路，在面试中的二叉树题目就应该没有什么问题。这里还有一篇关于二叉树的文章，
android SDK使用者、XCode用户、各种ide收集者、github搬运工、高级CV战士！！！第6章树和二叉树；1．选择题；（1）把一棵树转换为二叉树后，这棵二叉树的形态是；C．有多种，但根结点都没有左孩子Ｄ．有多种，但根；（3）一棵完全二叉树上有1001个结点，其中叶子；A．11B．10C．11至1025之间D．10至；k-1kh-1h；A．mB．m-1C．mD．m-1（6）利用二叉链；A．指向最左孩子B．指向最右孩子C．空D．非空；（7）对二叉树
树和二叉树 1．选择题 （1）把一棵树转换为二叉树后，这棵二叉树的形态是（
Ｂ．有多种 C．有多种，但根结点都没有左孩子
Ｄ．有多种，但根结点都没有右孩子 （2）由3 个结点可以构造出多少种不同的二叉树？（
（3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（
）。 A．250
（4）一个具有1025个结点的二叉树的高h为（
）。 A．11
C．11至1025之间
D．10至1024之间 （5）深度为h的满m叉树的第k层有（
）个结点。(1=<k=<h)
k-1 kh-1hA．m
D．m-1 （6）利用二叉链表存储树，则根结点的右指针是（
）。 A．指向最左孩子
B．指向最右孩子
D．非空 （7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（
）遍历实现编号。 A．先序
D. 从根开始按层次遍历 （8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（
）遍历方法最合适。 A．前序
D．按层次 （9）在下列存储形式中，（
）不是树的存储形式？ A．双亲表示法
B．孩子链表表示法
C．孩子兄弟表示法
D．顺序存储表示法 （10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（
）。 A．所有的结点均无左孩子
B．所有的结点均无右孩子 C．只有一个叶子结点
D．是任意一棵二叉树 （11）某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（
）的二叉树。 A．空或只有一个结点
B．任一结点无左子树
C．高度等于其结点数
D．任一结点无右子树 （12）若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（
）。 A．X的双亲
B．X的右子树中最左的结点
C．X的左子树中最右结点
D．X的左子树中最右叶结点 （13）引入二叉线索树的目的是（
）。 A．加快查找结点的前驱或后继的速度
B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲
D．使二叉树的遍历结果唯一 （14）线索二叉树是一种（
）结构。 A．逻辑
B． 逻辑和存储
D．线性 （15）设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（
）个。 A． n-1
2．应用题 （1）试找出满足下列条件的二叉树 ① 先序序列与后序序列相同
②中序序列与后序序列相同 ③ 先序序列与中序序列相同
④中序序列与层次遍历序列相同 先序遍历二叉树的顺序是“根―左子树―右子树”，中序遍历“左子树―根―右子树”，后序遍历顺序是：“左子树―右子树D根＂，根据以上原则，本题解答如下： （１）
若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树 （２）
若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树． （３）
若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树． （４）
若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树
（2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C ①画出这棵二叉树。 ②画出这棵二叉树的后序线索树。 ③将这棵二叉树转换成对应的树（或森林）。
(2) （3） 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 ① 试为这8个字母设计赫夫曼编码。 ② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例，比较两种方案的优缺点。 解：方案1；哈夫曼编码 先将概率放大100倍，以方便构造哈夫曼树。
w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ??19, 21, 32
1 （17） （11） 19 21
方案比较：
字母对应出现字母对应出现 编号 编码 频率 编号 编码 频率
1 000 0.07
2 00 0.19 2 001 0.19
3 010 0.02
4 011 0.06
10 0.32 5 100 0.32
5 6 101 0.03
方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 结论：哈夫曼编码优于等长二进制编码
（4）已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。
weight parent lchild rchild
2 12 0 0 0
7 11 0 0 0
weight parent lchild rchild 1 2 3 4 5 6 7 8 9 10 11 12 13 3 12 7 4 2 8 11 5 9 15 20 27 47 8 12 10 9 8 10 11 9 11 12 13 13 0 0 0 0 0 0 0 0 5 4 3 9 2 11 0 0 0 0 0 0 0 1 8 6 7 10 12 终态
3．算法设计题 以二叉链表作为二叉树的存储结构，编写以下算法： （1）统计二叉树的叶结点个数。 int LeafNodeCount(BiTree T) {
if(T==NULL)
//如果是空树，则叶子结点个数为0
else if(T->lchild==NULL&&T->rchild==NULL)
//判断该结点是否是叶子结点（左孩子右孩子都为空），若是则返回1
return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); } （2）判别两棵树是否相等。 （3）交换二叉树每个结点的左孩子和右孩子。 void ChangeLR(BiTree &T) {
if(T->lchild==NULL&&T->rchild==NULL)
temp = T->
T->lchild = T->
T->rchild =
ChangeLR(T->lchild);
ChangeLR(T->rchild); } （4）设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。 void DoubleTraverse(BiTree T) {
if(T == NULL)
else if(T->lchild==NULL&&T->rchild==NULL)
DoubleTraverse(T->lchild);
DoubleTraverse(T->rchild);
} } （5）计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。 [题目分析] 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。 int Width(BiTree bt)//求二叉树bt的最大宽度 {if (bt==null) return (0);
//空二叉树宽度为0 else
{BiTree Q[];//Q是队列，元素为二叉树结点指针，容量足够大
front=1;rear=1;last=1;//front队头指针,rear队尾指针,last同层最右结点在队列中的位置
temp=0; maxw=0;
//temp记局部宽度, maxw记最大宽度
//根结点入队列
while(front<=last)
{p=Q[front++]; temp++; //同层元素数加1
if (p->lchild!=null)
Q[++rear]=p->
//左子女入队 if (p->rchild!=null)
Q[++rear]=p->
//右子女入队
if (front>last)
//一层结束，
{last= if(temp>maxw) maxw=//last指向下层最右元素, 更新当前最大宽度
return (maxw); 三亿文库包含各类专业文献、高等教育、外语学习资料、各类资格考试、行业资料、应用写作文书、数据结构二叉树习题含答案67等内容。　
　数据结构二叉树习题含答案_理学_高等教育_教育专区。第6章 树和二叉树 1.选择题 (1)把一棵树转换为二叉树后,这棵二叉树的形态是( )。 A.唯一的 B.有多... 　第6章_数据结构习题题目及答案_树和二叉树_参考答案_计算机软件及应用_IT/计算机_专业资料。一、基础知识题 6.1 设树 T 的度为 4,其中度为 1,2,3 和 4... 　《数据结构》期末复习题及参考答案 - 第6章 树和二叉树【HSH2013级】给学生_工学_高等教育_教育专区。《数据结构》期末复习题及参考答案 - 第 6 章 树和... 　数据结构第六章树和二叉树习题及答案_计算机软件及应用_IT/计算机_专业资料。数据结构第六章树和二叉树习题及答案 习题六 树和二叉树一、单项选择题 1. 以下... 　数据结构考研复习题第六章--数和二叉树(带答案)_研究生入学考试_高等教育_教育专区。数据结构考研复习题第六章--数和二叉树(带答案)第... 　数据结构复习题附答案_工学_高等教育_教育专区。数据结构复习题,带有答案和解析...a:按层遍历 b:前序遍历 c:中序遍历 d:后序遍历 19 设一棵二叉树 BT 的... 　数据结构第6章二叉树自测题参考答案_电脑基础知识_IT/计算机_专业资料。数据结构第6章二叉树自测题参考答案 第6章 树和二叉树 自测卷解答 一、下面是有关二叉树... 　数据结构 第6章习题答案_IT认证_资格考试/认证_教育专区。数据结构 第6章 树和二叉树 习题解答 一、下面是有关二叉树的叙述,请判断正误(每小题 1 分,共 10...安全检查中...
请打开浏览器的javascript，然后刷新浏览器
< 浏览器安全检查中...
还剩 5 秒&