专栏来源 本专栏来自左程云著：《程序员代码面试指南》书，已获得官方授权。 本专栏为书中前三章内容，后续内容可购书学习哦，购书链接：https://item.jd.com/12518392.html?utm_source=blog.nowcoder.net&utm_medium=tuiguang&utm_campaign=t_2010959725_&utm_term=cbb9cb5476af4bbd89128cbbc35c4f40 在线OJ 本书官方OJ：https://www.nowcoder.com/ta/programme...

二叉树节点间的最大距离问题 【题目】 从二叉树的节点A出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点B时，路径上的节点数叫作A到B的距离。 比如，图3-43所示的二叉树，节点4和节点2的距离为2，节点5和节点6的距离为5。给定一棵二叉树的头节点head，求整棵树上节点间的最大距离。 【要求】 如果二叉树的节点数为N，时间复杂度要求为O(N)。 【难度】 尉     ★★☆☆ 【解答】 本题解法的整体过程为树形dp套路，请读者先阅读本书“找到二叉树中的最大搜索二...

在二叉树中找到一个节点的后继节点 【题目】 现在有一种新的二叉树节点类型如下：   public class Node { public int value; public Node left; public Node right; public Node parent; public Node(int data) { this.value = data; } } 该...

判断t1树是否包含t2树全部的拓扑结构 【题目】 给定彼此独立的两棵树头节点分别为t1和t2，判断t1树是否包含t2树全部的拓扑结构。 例如，如图3-34所示的t1树和如图3-35所示的t2树。 t1树包含t2树全部的拓扑结构，所以返回true。 【难度】 士     ★☆☆☆ 【解答】 如果t1中某棵子树头节点的值与t2头节点的值一样，则从这两个头节点开始匹配，匹配的每一步都让t1上的节点跟着t2上的节点的先序遍历移动，每移动一步，都检查t1的当前节点是否与t2当前节点的值一样。...

二叉树的按层打印与ZigZag打印 【题目】 给定一棵二叉树的头节点head，分别实现按层和ZigZag打印二叉树的函数。 例如，二叉树如图3-29所示。 按层打印时，输出格式必须如下：   Level 1 : 1 Level 2 : 2 3 Level 3 : 4 5 6 Level 4 : 7 8   ZigZag打印时，输出格式必须如下：   Level 1 from left to right: 1 Level 2 from right to left: 3...

在二叉树中找到累加和为指定值的最长路径长度 【题目】 给定一棵二叉树的头节点head和一个32位整数sum，二叉树节点值类型为整型，求累加和为sum的最长路径长度。路径是指从某个节点往下，每次最多选择一个孩子节点或者不选所形成的节点链。 例如，二叉树如图3-16所示。 如果sum=6，那么累加和为6的最长路径为：-3，3，0，6，所以返回4。 如果sum=-9，那么累加和为-9的最长路径为：-9，所以返回1。 注：本题不用考虑节点值相加可能溢出的情况。 【难度】 尉 ★★☆☆ 【解答】 在阅读本题的解答之前，...

如何较为直观地打印二叉树 【题目】 二叉树可以用常规的三种遍历结果来描述其结构，但是不够直观，尤其是二叉树中有重复值的时候，仅通过三种遍历的结果来构造二叉树的真实结构更是难上加难，有时则根本不可能。给定一棵二叉树的头节点head，已知二叉树节点值的类型为32位整型，请实现一个打印二叉树的函数，可以直观地展示树的形状，也便于画出真实的结构。 【难度】 尉     ★★☆☆ 【解答】 这是一道较开放的题目，实现者不仅要设计出符合要求且不会产生歧义的打印方式，还要考虑实现难度，在面试时仅仅写出思路必然是不满足代码面...

分别用递归和非递归方式实现二叉树先序、中序和后序遍历 【题目】 用递归和非递归方式，分别按照二叉树先序、中序和后序打印所有的节点。我们约定：先序遍历顺序为根、左、右；中序遍历顺序为左、根、右；后序遍历顺序为左、右、根。 【难度】 校     ★★★☆ 【解答】 用递归方式实现三种遍历是教材上的基础内容，本书不再详述，直接给出代码实现。 先序遍历的递归实现请参看如下代码中的preOrderRecur方法。 public class Node { public&...

在单链表中删除指定值的节点 【题目】 给定一个链表的头节点head和一个整数num，请实现函数将值为num的节点全部删除。 例如，链表为1->2->3->4->null，num=3，链表调整后为：1->2->4->null。 【难度】 士     ★☆☆☆ 【解答】 方法一：利用栈或者其他容器收集节点的方法。时间复杂度为O(N)，额外空间复杂度为O(N)。 将值不等于num的节点用栈收集起来，收集完成后重新连接即可。最后将栈底的节点作为新的头节点返回，具体过程请参看如下代码中的removeValue1方法...

两个单链表相交的一系列问题 【题目】 在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点head1和head2，这两个链表可能相交，也可能不相交。请实现一个函数，如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null即可。 要求：如果链表1的长度为N，链表2的长度为M，时间复杂度请达到O(N+M)，额外空间复杂度请达到O(1)。 【难度】 将     ★★★★ 【解答】 这道题需要分析的情况非常多，同时因为有额外空间复杂度为O(1)的限制，所以实现起来也比较困难。 本题可以拆分成三个子问题，每个问题都可以作为一道独立...

将单向链表按某值划分成左边小、中间相等、右边大的形式 【题目】 给定一个单向链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。除这个要求外，对调整后的节点顺序没有更多的要求。 例如：链表9->0->4->5->1，pivot=3。 调整后链表可以是1->0->4->9->5，也可以是0->1->9->5->4。总之，满足左部分都是小于3的节点，...

环形单链表的约瑟夫问题 【题目】 据说著名犹太历史学家Josephus有过以下故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种***方式，41个人排成一个圆圈，由第1个人开始报数，报数到3的人就***，然后再由下一个人重新报1，报数到3的人再***，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表描述该结构并呈现整个***过程。 输入：一个环形单向链表的头节点head和报数的值m。 返回：最后生存下来的节点，且...

打印两个有序链表的公共部分 【题目】 给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。 【难度】 士     ★☆☆☆ 【解答】 本题难度很低，因为是有序链表，所以从两个链表的头开始进行如下判断： — 如果head1的值小于head2，则head1往下移动。 — 如果head2的值小于head1，则head2往下移动。 — 如果head1的值与head2的值相等，则打印这个值，然后head1与head2都往下移动。 — head1或head2有任何一个移动到null，则整个过程停止。 具体过程参看如下代码...

最大值减去最小值小于或等于num的子数组数量 【题目】 给定数组arr和整数num，共返回有多少个子数组满足如下情况： max(arr[i..j]) - min(arr[i..j]) <= num max(arr[i..j])表示子数组arr[i..j]中的最大值，min(arr[i..j])表示子数组arr[i..j]中的最小值。 【要求】 如果数组长度为N，请实现时间复杂度为O(N)的解法。 【难度】 校     ★★★☆ 【解答】 首先介绍普通的解法，找到arr的所有子数组，一共有O(N2)个，然后对每一个子数组做遍历找到...