1、思路 多叉树问题，每名员工有若干个直接下级员工，除老板外，每名员工都有唯一的直接上级； 某一级节点来不来参加派对，要看这级节点来还是不来两种情况下，哪一种获得的收益最多，分两种情况： 1、当前节点来参加派对收的益 = 当前节点的快乐值 + 其所有子节点不来参加派对的收益之和（注意：子节点不来参加派对的收益不一定为0，因为它的孙子节点可能来参加，这种情况要递归计算）； 2、当前节点不来参加派对的收益 = max(子节点来参加派对的收益， 子节点不来参加派对的收益)。 2、代码 #include <iostream> #include <vector> ...

1、思路 树形DP套路第一步：分析答案来自哪些可能性： 1、以root为头节点的子树，最大距离可能是左子树上的最大距离； 2、以root为头节点的子树，最大距离可能是右子树上的最大距离； 3、以root为头节点的子树，最大距离可能是左子树上高度 + 右子树高度 + 1（root节点本身）； 第二步：根据第一步的分析列出所有需要的信息，左子树和右子树需要知道自己这棵子树上的最大距离 maxDistance 以及高度 height这两个信息； 第三步：根据第二步的信息汇总，用一个新的结构体 ReturnType来存储上述两个信息； 第四步：设计递归函数，整合信息。 2、代码...

1、思路 对二叉树进行前序遍历，找到目标节点后就返回该节点； 每次递归分三种情况讨论： 1、若当前节点的左右子树返回值都不为空，则当前节点即是最近公共祖先； 2、若只有左子树返回值不为空，说明其中一个节点或者两个节点都在左子树，直接返回左子树的返回值； 3、若只有右子树返回值不为空，同上。 2、代码 #include <iostream> using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int _val) : val(_...

1、思路 对于二叉搜索树的判断，可以在中序遍历时保存前一个节点的值，每次比较当前节点值与前一节点值，若前一节点值较大，则该二叉树不是二叉搜索树； 对于完全二叉树的判断，可以按照以下标准进行： 1、层序遍历二叉树； 2、若当前节点有右子节点却没有左子节点，则直接返回false； 3、若当前节点并不是左右孩子都有，那么之后的节点必须都为叶子结点，否则返回false； 4、遍历过程中若不返回false，则遍历结束后返回true。 2、代码 #include <iostream> #include <stack> #include <queue&g...

1、思路 二叉树的后序遍历为先左、再右、最后根的顺序，即二叉树的头节点值为数组的最后一个元素； 例如数组 [2, 1, 3, 6, 5, 7, 4]，比4小的部分为[2, 1, 3]，比4大的部分为[6, 5, 7]，再继续递归地判断这两部分子树。 2、代码 #include <iostream> #include <vector> using namespace std; bool isPostOrder(vector<int>& nums, int st, int ed) { if (st == ed) { ...

1、思路 用一个 getDeep 函数计算当前子树的深度； 每次递归都要判断 root 的左右子树是否平衡，并判断以 root 为根节点的子树是否平衡。 2、代码 #include <iostream> using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {} }; void createTree(TreeNode *root, ...

1、思路 按照二叉树的中序遍历顺序，将每个节点放入队列q中； 从q中依次弹出节点，并按照弹出的顺序重新连接所有节点即可。 2、代码 double_list_node * convert(BST * root) { queue<BST*> q; inOrderTreeToQueue(root, q); root = q.front(); q.pop(); // head 为双链表头结点 double_list_node *head = new double_list_node(), *pre = head; pre-...

1、思路 若树root1中某棵子树节点的值与树root2头节点的值一样，则从这两个头节点开始匹配，匹配的每一步都让root1上的节点跟着root2上的节点的先序遍历移动，每移动一步都检查两棵树当前节点的值是否相同； 因为root1的每棵子树上都可能匹配出root2，所以都要检查一边，故时间复杂度为 ，其中 和 分别为root1与root2的节点个数。 2、代码 #include <iostream> using namespace std; struct TreeNode //二叉树节点 { int ...

1、思路 我们先考查root的孩子节点，根据孩子节点的值从root开始按照二叉搜索的方式移动，如果最后能移动到同一个孩子节点上，说明这个孩子节点可以作为这个拓扑的一部分，并继续考察这个孩子节点的孩子节点，一直延伸下去； 时间复杂度为 。 2、代码 #include <iostream> using namespace std; struct TreeNode //二叉树节点 { int val; TreeNode *left, *right; TreeNode(int _val) : v...

1、思路 书中描述的方法稍显复杂，这里用一种更简单的思路： 快慢指针指向头结点，快指针先往前移动K步； 若快指针遍历完链表后，K大于0，表示K的值已经超过了链表本身的长度，即不存在倒数第K个节点； 快慢指针同时往前走，快指针走到链表尾部时，慢指针所指的就是倒数第K个节点。因为慢指针比快指针少走了K步，故快指针走完链表时，慢指针刚好走到链表的倒数第K个节点。 2、代码 list_node * remove_last_kth_node(list_node * head, int K) { auto fast = head, slow = head; while (K -...

1、思路 打印所有公共的部分，不止是连续的公共部分，用两个指针a与b从头遍历两个升序链表： 若a的值小于b，则a往下移动； 若b的值小于a，则b往下移动； 若a的值等于b，则打印该值，且两个指针都往下移动一步。 2、代码 #include <iostream> #include <memory> //包含了智能指针库 using namespace std; struct ListNode{ int val; shared_ptr<ListNode> next; ListNode(int _val) : val(_...

1、思路 当环形结构中只有一座山峰时，可见山峰对数量为0。当有两座时，可见山峰对数量为1。当有三座时可见山峰对数量为3。可以推导得出当有n座山峰时，可见山峰对数量为2 * n - 3； 假设环形结构中有n座山峰，除了最高山峰和次高山峰外还剩下n - 2座山峰，这n - 2座山峰中每一座都能根据小找大的方式找到两对，所以一共有(i - 2) * 2对，再加上最高山峰和次高山峰这对，一共就有2 * n - 3对。 2、代码 #include <iostream> using namespace std; int main() { int T; cin &gt...

1、思路 对二叉树进行中序遍历得到的节点值是升序的，若出现降序的情况，说明找到了错误的节点，降序分两种情况讨论： 1、中序遍历时节点值出现两次降序，如[1, 5, 3, 4, 2]，第一次降序为5->3，第二次降序为4->2； 2、中序遍历时节点值出现一次降序，如[1, 2, 4, 3, 5]，只有一次降序为4->3； 寻找两个错误节点的过程可以总结为：第一个错误节点为第一次降序时较大的节点，第二个错误节点为最优一次降序时较小的节点。 2、代码 #include #include #include using namespace std; struct ...

1、思路 需要求出以每一个节点为头节点的子树的最大搜索二叉子树。对于每一个节点，我们用一个结构体ReturnType来保存该节点的四种信息：1、maxBSTHead 该子树中最大二叉搜索树的头节点；2、maxBSTSize 该子树中最大二叉搜索树的节点个数；3、min 该子树中最小节点值；4、max 该子树中最大节点值； 以节点 root 为头节点的子树中，最大搜索二叉子树只可能有三种情况：1、最大搜索二叉子树是root左子树中的最大搜索二叉子树，即答案来自左子树；2、最大搜索二叉子树是root右子树中的最大搜索二叉子树，即答案来自右子树；3、最大搜索二叉子树是以root为头节点的子树，即...