求二叉树中节点的最大距离

二叉树知识点总结1. 二叉树的性质1.1 二叉树的性质一：二叉树的深度二叉树的深度是指从根节点到叶子节点的最长路径长度。

对于一个空树而言，它的深度为0；对于只有一个根节点的树而言，它的深度为1。

根据定义可知，深度为k的二叉树中，叶子节点的深度值为k。

由此可知，二叉树的深度为所有叶子节点深度的最大值。

1.2 二叉树的性质二：二叉树的高度二叉树的高度是指从根节点到叶子节点的最短路径长度。

对于一个空树而言，它的高度为0；对于只有一个根节点的树而言，它的高度为1。

由此可知，二叉树的高度总是比深度大一。

1.3 二叉树的性质三：二叉树的节点数量对于一个深度为k的二叉树而言，它最多包含2^k - 1个节点。

而对于一个拥有n个节点的二叉树而言，它的深度最多为log2(n+1)。

1.4 二叉树的性质四：满二叉树满二叉树是一种特殊类型的二叉树，它的每个节点要么是叶子节点，要么拥有两个子节点。

满二叉树的性质是：对于深度为k的满二叉树而言，它的节点数量一定是2^k - 1。

1.5 二叉树的性质五：完全二叉树完全二叉树是一种特殊类型的二叉树，它的所有叶子节点都集中在树的最低两层，并且最后一层的叶子节点从左到右依次排列。

对于一个深度为k的完全二叉树而言，它的节点数量一定在2^(k-1)和2^k之间。

2. 二叉树的遍历二叉树的遍历是指按照一定的顺序访问二叉树的所有节点。

二叉树的遍历主要包括前序遍历、中序遍历和后序遍历三种。

2.1 前序遍历（Pre-order traversal）前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

对于一个二叉树而言，前序遍历的结果就是按照“根-左-右”的顺序访问所有节点。

2.2 中序遍历（In-order traversal）中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

对于一个二叉树而言，中序遍历的结果就是按照“左-根-右”的顺序访问所有节点。

2.3 后序遍历（Post-order traversal）后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

20091.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。

若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。

设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是I．父子关系II.兄弟关系III.u的父结点与v的父结点是兄弟关系A.只有IIB.I和IIC.I和IIID.I、II和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I和IID.I和III8.下列叙述中，不符合m阶B树定义要求的是A．根节点最多有m棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。

《编程之美》求二叉树中节点的最大距离问题定义(动态规划)如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。

写一个程序求一棵二叉树中相距最远的两个节点之间的距离。

书上的解法书中对这个问题的分析是很清楚的，我尝试用自己的方式简短覆述。

计算一个二叉树的最大距离有两个情况:情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。

情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。

只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离。

我也想不到更好的分析方法。

但接着，原文的实现就不如上面的清楚(源码可从这里下载):1234 5 6 7 8 9101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081// 数据结构定义structNODE{NODE* pLeft;// 左子树NODE* pRight;// 右子树intnMaxLeft;// 左子树中的最长距离intnMaxRight;// 右子树中的最长距离charchValue;// 该节点的值};intnMaxLen = 0;// 寻找树中最长的两段距离voidFindMaxLen(NODE* pRoot){// 遍历到叶子节点，返回if(pRoot == NULL){return;}// 如果左子树为空，那么该节点的左边最长距离为0 if(pRoot -> pLeft == NULL){pRoot -> nMaxLeft = 0;}// 如果右子树为空，那么该节点的右边最长距离为0 if(pRoot -> pRight == NULL){pRoot -> nMaxRight = 0;}// 如果左子树不为空，递归寻找左子树最长距离if(pRoot -> pLeft != NULL){FindMaxLen(pRoot -> pLeft);}// 如果右子树不为空，递归寻找右子树最长距离if(pRoot -> pRight != NULL){FindMaxLen(pRoot -> pRight);}// 计算左子树最长节点距离if(pRoot -> pLeft != NULL){intnTempMax = 0;if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight) {nTempMax = pRoot -> pLeft -> nMaxLeft;}else{nTempMax = pRoot -> pLeft -> nMaxRight;}pRoot -> nMaxLeft = nTempMax + 1;}// 计算右子树最长节点距离if(pRoot -> pRight != NULL){intnTempMax = 0;if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight) {nTempMax = pRoot -> pRight -> nMaxLeft;}else{nTempMax = pRoot -> pRight -> nMaxRight;}pRoot -> nMaxRight = nTempMax + 1;}// 更新最长距离if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen){nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;}}这段代码有几个缺点:算法加入了侵入式(intrusive)的资料nMaxLeft, nMaxRight使用了全局变量nMaxLen。

1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的结点，只调整指针的指向。

10/ \6 14/ \ / \4 8 12 16转换成双向链表4=6=8=10=12=14=16。

首先我们定义的二元查找树节点的数据结构如下：struct BSTreeNode{int m_nValue; // value of nodeBSTreeNode *m_pLeft; // left child of nodeBSTreeNode *m_pRight; // right child of node};2.设计包含min函数的栈。

定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。

要求函数min、push以及pop的时间复杂度都是O(1)。

3.求子数组的最大和题目：输入一个整形数组，数组里有正数也有负数。

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

求所有子数组的和的最大值。

要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

4.在二元树中找出和为某一值的所有路径题目：输入一个整数和一棵二元树。

从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。

打印出和与输入整数相等的所有路径。

例如输入整数22和如下二元树10/ \5 12/ \4 7则打印出两条路径：10, 12和10, 5, 7。

二元树节点的数据结构定义为：struct BinaryTreeNode // a node in the binary tree{int m_nValue; // value of nodeBinaryTreeNode *m_pLeft; // left child of nodeBinaryTreeNode *m_pRight; // right child of node};5.查找最小的k个元素题目：输入n个整数，输出其中最小的k个。

第三章 互连网络3.1 对于一颗K 级二叉树（根为0级，叶为k-1级）,共有N=2^k —1个节点，当推广至m —元树时（即每个非叶节点有m 个子节点)时,试写出总节点数N 的表达式。

答:推广至M 元树时，k 级M 元树总结点数N 的表达式为：N=1+m^1+m^2+。

.。

+m^（k —1）=(1—m^k)*1/(1-m);3.2二元胖树如图3.46所示，此时所有非根节点均有2个父节点.如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。

试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络？ 答：8输入的完全混洗三级互联网络.3.3 四元胖树如图3.47所示，试问：每个内节点有几个子节点和几个父节点?你知道那个机器使用了此种形式的胖树？答:每个内节点有4个子节点，2个父节点。

CM —5使用了此类胖树结构.3.4 试构造一个N=64的立方环网络,并将其直径和节点度与N=64的超立方比较之,你的结论是什么?答：A N=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=4B N=64的超立方网络,为六维超立方(将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方)，直径d=6，节点度n=63.5 一个N=2^k 个节点的 de Bruijin 网络如图3。

48。

个节点的二进制表示，。

试问:该网络的直径和对剖宽度是多少？答：N=2^k 个节点的 de Bruijin 网络 直径d=k 对剖宽带w=2^(k-1）3.6 一个N=2^n 个节点的洗牌交换网络如图3.49所示.试问：此网络节点度==?网络直径==？网络对剖宽度==？答：N=2^n 个节点的洗牌交换网络,网络节点度为=2 ，网络直径=n —1 ,网络对剖宽度=43.7 一个N=（k+1)2^k 个节点的蝶形网络如图3.50所示.试问:此网络节点度=？网络直径=?网络对剖宽度=?答：N=（k+1）2^k 个节点的蝶形网络,网络节点度=4 ，网络直径=2＊k ，网络对剖宽度=2^k3。

⼆叉树常见⾯试题（进阶）⼀、常见题型1. 求两个节点的最近公共祖先；2. 求⼆叉树中最远的两个节点的距离；3. 由前序遍历和中序遍历重建⼆叉树（如：前序序列：1 2 3 4 5 6 - 中序序列：3 2 4 1 6 5）；4. 判断⼀棵树是否是完全⼆叉树；5. 将⼆叉搜索树转换成⼀个排序的双向链表。

要求不能创建任何新的结点，只能调整树中结点指针的指向；6.求⼆叉树的宽度；7. 判断⼀棵⼆叉树是否是平衡⼆叉树；8.判断⼀颗⼆叉树是否是另⼀颗树的⼦树。

⼆、解题思路分析1.两个节点的最近公共祖先求两个节点的最近公共祖先可分为三种情况，分别为：（1）求搜索⼆叉树的最近公共祖先。

根据搜索⼆叉树的性质，左⼦树的所有节点⽐根节点⼩，右⼦树的所有节点⽐跟节点⼤。

如果两个节点都⽐根节点⼩，则递归左⼦树；如果两个节点都⽐跟节点⼤，则递归右⼦树；否则，两个节点⼀个在左⼦树，⼀个在右⼦树，则当前节点就是最近公共祖先节点。

1 Node* GetAncestor(Node* root, Node* x1, Node* x2)//1.该⼆叉树为搜索⼆叉树2 {3 assert(x1 && x2);4if (x1->_data <= root->_data && x2->_data <= root->_data)5 {6return GetAncestor(root->_left, x1, x2);//两个节都⼩于根节点，最近公共祖先在左⼦树中7 }8else if (x1->_data > root->_data && x2->_data > root->_data)9 {10return GetAncestor(root->_right, x1, x2);//两个节都⼤于根节点，最近公共祖先在左⼦树中11 }12else13return root; //⼀个在左⼦树，⼀个在右⼦树，找到公共祖先1415 }（2）三叉链，带⽗节点时求最近公共祖先，⼆叉树节点有指向⽗节点的指针。

九章算法前⾔第⼀天的算法都还没有缓过来，直接就进⼊了第⼆天的算法学习。

前⼀天⼀直在整理Binary Search的笔记，也没有提前预习⼀下，好在Binary Tree算是⾃⼰最熟的地⽅了吧（LeetCode上⾯Binary Tree的题刷了4遍，⽬前95%以上能够Bug Free）所以还能跟得上，今天听了⼀下，觉得学习到最多的，就是把Traverse和Divide Conquer分开来讨论，觉得开启了⼀⽚新的天地！今天写这个博客我就尽量把两种⽅式都写⼀写吧。

Outline:⼆叉树的遍历前序遍历traverse⽅法前序遍历⾮递归⽅法前序遍历分治法遍历⽅法与分治法Maximum Depth of Binary TreeBalanced Binary Tree⼆叉树的最⼤路径和 (root->leaf)Binary Tree Maximum Path Sum II (root->any)Binary Tree Maximum Path Sum (any->any)⼆叉查找树Validate Binary Search TreeBinary Search Tree Iterator⼆叉树的宽度优先搜索Binary Tree Level-Order Traversal课堂笔记1.⼆叉树的遍历这个应该是⼆叉树⾥⾯最基本的题了，但是在⾯试过程中，不⼀定会考递归的⽅式，很有可能会让你写出⾮递归的⽅法，上课的时候⽼师也提到过，应该直接把⾮递归的⽅法背下来。

这⾥我就不多说了，直接把中序遍历的两种⽅法贴出来吧，最后再加⼊⼀个分治法（这也是第⼀次写，感觉很棒呢，都不需要太多的思考）。

1.1 前序遍历traverse⽅法（Bug Free）：vector<int> res;void helper(TreeNode* root) {if (!root) return;res.push_back(root->val);if (root->left) {helper(root->left);}if (root->right) {helper(root->right);}}vector<int> preorderTraversal(TreeNode *root) {if (!root) {return res;}helper(root);return res;}1.2 前序遍历⾮递归⽅法（Bug Free）：vector<int> preorderTraversal(TreeNode *root) {vector<int> res;if (!root) {return res;}stack<TreeNode*> s;s.push(root);while (!s.empty()) {TreeNode* tmp = s.top();s.pop();res.push_back(tmp->val);// 这⾥注意：栈是先进后出，所以先push右⼦树if (tmp->right) {s.push(tmp->right);}if (tmp->left) {s.push(tmp->left);}}return res;}1.3 前序遍历分治法（Java实现）：vector<int> preorderTraversal(TreeNode *root) {vector<int> res;if (!root) {return res;}//Dividevector<int> left = preorderTraversal(root->left);vector<int> right = preorderTraversal(root->right);//Conquerres.push_back(root->val);res.insert(res.end(), left.begin(), left.end());res.insert(res.end(), right.begin(), right.end());return res;}这三种⽅法也是⽐较直观的，前两个⽐较基础，我就不详细叙述了，但是分治法是值得重点说⼀说的。

【字符串】1、输入一个字符串，打印出该字符串中字符的所有排列。

例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

2、有一个由大小写组成的字符串，现在需要对他进行修改，将其中的所有小写字母排在大写字母的前面（大写或小写字母之间不要求保持原来次序），如有可能尽量选择时间和空间效率高的算法。

c语言函数原型void proc（char *str），也可以采用你自己熟悉的语言。

3、编写反转字符串的程序，要求优化速度、优化空间。

4、用C语言实现函数void * memmove(void *dest, const void *src, size_t n)。

memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。

分析：由于可以把任何类型的指针赋给void类型的指针，这个函数主要是实现各种数据类型的拷贝。

5、编程找出两个字符串中最大公共子字符串,如"abccade", "dgcadde"的最大子串为"cad"。

6、输入一个字符串，输出该字符串中对称的子字符串的最大长度。

比如输入字符串"google"，由于该字符串里最长的对称子字符串是"goog"，因此输出4。

7、字符串原地压缩。

题目描述：“eeeeeaaaff" 压缩为"e5a3f2"，请编程实现。

8、请以回溯与不回溯算法实现字符串匹配。

9、输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。

句子中单词以空格符隔开。

为简单起见，标点符号和普通字母一样处理。

例如：输入"I am a student."，则输出"student. a am I"。

10、在一个字符串中找到第一个只出现一次的字符。

如输入abaccdeff，则输出b。

树和二叉树习题及答案一、填空题1. 不相交的树的聚集称之为森林。

2. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_树可采用孩子-兄弟链表（二叉链表）做存储结构，目的是利用二叉树的已有算法解决树的有关问题。

3. 深度为k的完全二叉树至少有2 k-1个结点。

至多有2 k-1个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是2 k-2+1。

4. 在一棵二叉树中，度为零的结点的个数为n，度为2的结点的个数为n2，则有n= n2+1。

5. 一棵二叉树的第i（i≥1）层最多有2 i-1个结点；一棵有n （n>0）个结点的满二叉树共有（n+1）/2个叶子和（n-1）/2个非终端结点。

6.现有按中序遍历二叉树的结果为abc，问有5种不同形态的二叉树可以得到这一遍历结果。

7. 哈夫曼树是带权路径最小的二叉树。

8. 前缀编码是指任一个字符的编码都不是另一个字符编码的前缀的一种编码方法，是设计不等长编码的前提。

9. 以给定的数据集合{4，5，6，7，10，12，18}为结点权值构造的Huffman树的加权路径长度是 165 。

10. 树被定义为连通而不具有回路的（无向）图。

11. 若一棵根树的每个结点最多只有两个孩子，且孩子又有左、右之分，次序不能颠倒，则称此根树为二叉树。

12. 高度为k，且有个结点的二叉树称为二叉树。

2k-1 满13. 带权路径长度最小的二叉树称为最优二叉树，它又被称为树。

Huffman14. 在一棵根树中，树根是为零的结点，而为零的结点是结点。

入度出度树叶15. Huffman树中，结点的带权路径长度是指由到之间的路径长度与结点权值的乘积。

结点树根16. 满二叉树是指高度为k，且有个结点的二叉树。

二叉树的每一层i上，最多有个结点。

2k-1 2i-1二、单选题1. 具有10个叶结点的二叉树中有 (B) 个度为2的结点。

(A)8 (B)9 (C)10 (D)112．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_（3）次序的遍历实现编号。