it公司面试汇总

《it公司面试汇总》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1.题目：二叉树，各边有不同权值，求一路径，使得两点之间路径的所有边的权重之和最大，路径中边不重复，问复杂度多少？分析：编程之美3.8有过解答，时间复杂度为O(v)。但是这里有点不同：树的边有权值。第一种解法：最大距离的节点一定是叶子节点，首先将二叉树看成一个连通图，首先应该求根节点到所有叶节点的最大距离叶节点A，然后求A到所有其他节点的最大距离。假设要求节点A到其他节点之间的最长路径，题目的转换为求解以A为源点的最长路径。采用单源最短路径（dijkstra）的思想求解。这里要求最长路径，因此，每次选择时，应该从未知最大距离的节点集合中选择最大距离的节点加入

2、已知最大距离的节点集合。如果采用堆结构来维护未知节点到A的最大距离，那么时间复杂度为O（vlogv）。第二种解法：采用编程之美3.8节的递归方法，递归遍历二叉树一次，得出最大距离，时间复杂度为O（v）2.判断两颗二叉树是否相等，注意：相等包含两种：以下任意一种成立，root1和root2相等。·1.root1的左子树与root2的左子树相同并且root1的右子树与root2的右子树相同。·1.root1的左子树与root2的左子树相同并且root1的右子树与root2的右子树相同。分析：按照上述两种情况写出递归即可。viewplaincopytoclipbo

3、ardprint?1.2.boolIsBSTEqual(BNode*root1,BNode*root2)3.{4.if(root1==NULL&&root2==NULL)5.{6.returntrue;7.}8.elseif(root1==NULL

4、

5、root2==NULL)9.{10.returnfalse;11.}12.else13.{14.if(root1->data!=root2->data)15.{16.returnfalse;17.}18.1.boolis_left=IsBSTEqual(root1->left,root2->left);2.bo

6、olis_right=IsBSTEqual(root1->right,root2->right);3.4.if(is_left&&is_right)5.returntrue;6.7.else8.{9.is_right=IsBSTEqual(root1->right,root2->left);10.is_left=IsBSTEqual(root1->left,root2->right);11.12.if(is_left&&is_right)13.returntrue;14.else15.returnfalse;16.}17.}18.19.}输入一颗二叉树根节点

7、，复制该树，返回新建树的根节点。分析：这一道题跟求二叉树的高度类似，使用后续遍历即可完成。参考代码如下：viewplaincopytoclipboardprint?1.2.classBNode3.{4.public:5.BNode()6.{7.left=NULL;8.right=NULL;9.}10.BNode*left;11.BNode*right;12.chardata;13.};14.15.BNode*CopyBST(BNode*root)16.{17.if(root==NULL)18.returnNULL;19.1.BNode*sub_tree=ne

8、wBNode;2.3.sub_tree->data=root->data;4.sub_tree->left=CopyBST(root->left);5.sub_tree->right=CopyBST(root->right);6.7.returnsub_tree;8.}题目：输入一棵二叉树的根结点，求该树的高度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的高度。分析：通过后序遍历二叉树的方式计算高度，每次从子树返回，选择子树高度大的值+1作为当前数的高度，递归实现，参考代码如下：viewplaincopytoclipb

9、oardprint?1.2.classBNode3.{4.public:5.BNode()6.{7.left=NULL;8.right=NULL;9.}10.BNode*left;11.BNode*right;12.chardata;13.};14.15.intBTreeHight(BNode*root)16.{17.if(!root)18.{19.return0;20.}21.intleft_subtree_height=BTreeHight(root->left);22.intright_subtree_height=BTreeHight(root->r

10、ight);23.intheight;24.if(l