我要出去乱说

分类

C++(2) 程序员代码面试指南(20) 题解(2)

/ 注册

TA的专栏 50篇文章 3人订阅

程序员代码面试指南（C++版题解）

41篇文章 592人学习

我的面经汇总

9篇文章 21585人学习

全部文章（共42篇）

程序员代码面试指南 3.20：二叉树节点间的最大距离问题来自专栏

1、思路树形DP套路第一步：分析答案来自哪些可能性： 1、以root为头节点的子树，最大距离可能是左子树上的最大距离； 2、以root为头节点的子树，最大距离可能是右子树上的最大距离； 3、以root为头节点的子树，最大距离可能是左子树上高度 + 右子树高度 + 1（root节点本身...

C++

2022-07-01

1 503

程序员代码面试指南 3.18：在二叉树中找两节点最近公共祖先来自专栏

1、思路对二叉树进行前序遍历，找到目标节点后就返回该节点；每次递归分三种情况讨论： 1、若当前节点的左右子树返回值都不为空，则当前节点即是最近公共祖先； 2、若只有左子树返回值不为空，说明其中一个节点或者两个节点都在左子树，直接返回左子树的返回值； 3、若只有右子树返回值不为空，...

C++

2022-07-01

1 346

程序员代码面试指南 3.15：判断一棵二叉树是否为搜索二叉树来自专栏

1、思路对于二叉搜索树的判断，可以在中序遍历时保存前一个节点的值，每次比较当前节点值与前一节点值，若前一节点值较大，则该二叉树不是二叉搜索树；对于完全二叉树的判断，可以按照以下标准进行： 1、层序遍历二叉树； 2、若当前节点有右子节点却没有左子节点，则直接返回false； 3、若...

C++

2022-06-29

1 592

程序员代码面试指南 3.14：根据后序数组重建搜索二叉树来自专栏

1、思路二叉树的后序遍历为先左、再右、最后根的顺序，即二叉树的头节点值为数组的最后一个元素；例如数组 [2, 1, 3, 6, 5, 7, 4]，比4小的部分为[2, 1, 3]，比4大的部分为[6, 5, 7]，再继续递归地判断这两部分子树。 2、代码 #include <ios...

C++

2022-06-29

1 401

程序员代码面试指南 3.13：判断二叉树是否为平衡二叉树来自专栏

1、思路用一个 getDeep 函数计算当前子树的深度；每次递归都要判断 root 的左右子树是否平衡，并判断以 root 为根节点的子树是否平衡。 2、代码 #include <iostream> using namespace std; struct TreeNode...

C++

2022-06-28

1 413

程序员代码面试指南 2.15：将搜索二叉树转换成双向链表来自专栏

1、思路按照二叉树的中序遍历顺序，将每个节点放入队列q中；从q中依次弹出节点，并按照弹出的顺序重新连接所有节点即可。 2、代码 double_list_node * convert(BST * root) { queue<BST*> q; inOrderTre...

C++

2022-06-28

1 382

程序员代码面试指南 3.11：判断是否包含全部的拓扑结构来自专栏

1、思路若树root1中某棵子树节点的值与树root2头节点的值一样，则从这两个头节点开始匹配，匹配的每一步都让root1上的节点跟着root2上的节点的先序遍历移动，每移动一步都检查两棵树当前节点的值是否相同；因为root1的每棵子树上都可能匹配出root2，所以都要检查一边，故时间复杂度...

C++

2022-06-27

1 460

程序员代码面试指南 3.8：找到二叉树符合条件的最大拓扑结构来自专栏

1、思路我们先考查root的孩子节点，根据孩子节点的值从root开始按照二叉搜索的方式移动，如果最后能移动到同一个孩子节点上，说明这个孩子节点可以作为这个拓扑的一部分，并继续考察这个孩子节点的孩子节点，一直延伸下去；时间复杂度为。 2、代码 #include <iostream...

C++

2022-06-27

1 452

程序员代码面试指南2.2：在链表中删除倒数第K个节点来自专栏

1、思路书中描述的方法稍显复杂，这里用一种更简单的思路：快慢指针指向头结点，快指针先往前移动K步；若快指针遍历完链表后，K大于0，表示K的值已经超过了链表本身的长度，即不存在倒数第K个节点；快慢指针同时往前走，快指针走到链表尾部时，慢指针所指的就是倒数第K个节点。因为慢指针比快指针少走...

C++

2022-06-26

1 349

程序员代码面试指南 2.1：打印两个升序链表的公共部分来自专栏

1、思路打印所有公共的部分，不止是连续的公共部分，用两个指针a与b从头遍历两个升序链表：若a的值小于b，则a往下移动；若b的值小于a，则b往下移动；若a的值等于b，则打印该值，且两个指针都往下移动一步。 2、代码 #include <iostream> #include...

C++

2022-06-26

1 421