共计 2948 个字符，预计需要花费 8 分钟才能阅读完成。
题目形容
这是「牛客网」上的 「JZ 57 二叉树的下一个结点」，难度为 「中等」。
Tag :「剑指 Offer」、「二叉树」、「中序遍历」
给定一个二叉树其中的一个结点，请找出中序遍历程序的下一个结点并且返回。
留神，树中的结点不仅蕴含左右子结点，同时蕴含指向父结点的 next 指针。
下图为一棵有 个节点的二叉树。树中从父节点指向子节点的指针用实线示意，从子节点指向父节点的用虚线示意。
示例:
| 输出:{8,6,10,5,7,9,11},8 | |
| 返回:9 | |
| 解析: 这个组装传入的子树根节点，其实就是整颗树，中序遍历 {5,6,7,8,9,10,11}，根节点 8 的下一个节点就是 9，应该返回 {9,10,11}，后盾只打印子树的下一个节点，所以只会打印 9，如下图，其实都有指向左右孩子的指针，还有指向父节点的指针，下图没有画进去。 |
输出形容：输出分为 2 段，第一段是整体的二叉树，第二段是给定二叉树节点的值，后盾会将这 2 个参数组装为一个二叉树部分的子树传入到函数 GetNext 外面，用户失去的输出只有一个子树根节点。
返回值形容：返回传入的子树根节点的下一个节点，后盾会打印输出这个节点。
示例 1
| 输出：{8,6,10,5,7,9,11},8 | |
| 返回值：9 |
示例 2
| 输出：{8,6,10,5,7,9,11},6 | |
| 返回值：7 |
示例 3
| 输出：{1,2,#,#,3,#,4},4 | |
| 返回值：1 |
示例 4
| 输出：{5},5 | |
| 返回值："null" | |
| 阐明：不存在，后盾打印 "null" |
要求：
- 工夫：1 s
- 空间：64 M
奢侈解法
一个奢侈的做法是，依据题目对于 TreeLinkNode 的定义，利用 next 属性存储「以后节点的父节点」这一特点。
从入参节点 pNode 登程，一直利用 next 属性往上查找，直到找到整棵树的头节点，令头节点为 root。
而后实现二叉树的「中序遍历」，将遍历过程中拜访的节点寄存到列表 list 中，之后再对 list 进行遍历，找到 pNode 所在的地位 idx，即可确定 pNode 是否存在「下一个节点」以及「下一节点」是哪一个。
代码：
| import java.util.*; | |
| public class Solution {List<TreeLinkNode> list = new ArrayList<>(); | |
| public TreeLinkNode GetNext(TreeLinkNode pNode) { | |
| // 依据传入的节点的 next 指针始终往上找，直到找到根节点 root | |
| TreeLinkNode root = pNode; | |
| while (root.next != null) root = root.next; | |
| // 对树进行一遍「中序遍历」，保留后果到 list 中 | |
| dfs(root); | |
| // 从 list 中找传入节点 pNode 的地位 idx | |
| int n = list.size(), idx = -1; | |
| for (int i = 0; i < n; i++) {if (list.get(i).equals(pNode)) { | |
| idx = i; | |
| break; | |
| } | |
| } | |
| // 如果 idx 不为「中序遍历」的最初一个元素，那么阐明存在下一个节点，从 list 查找并返回 | |
| // 这里的 idx == -1 的判断属于防御性编程 | |
| return idx == -1 || idx == n - 1 ? null : list.get(idx + 1); | |
| } | |
| void dfs(TreeLinkNode root) {if (root == null) return; | |
| dfs(root.left); | |
| list.add(root); | |
| dfs(root.right); | |
| } | |
| } |
- 工夫复杂度：找头节点
root最多拜访的节点数量不会超过树高；进行中序遍历的复杂度为；从中序遍历后果中找到pNode的下一节点的复杂度为。整体复杂度为 - 空间复杂度：疏忽递归带来的额定空间耗费。复杂度为
进阶解法
另外一个“进阶”的做法是充分利用「二叉树的中序遍历」来实现的。
咱们晓得，二叉树「中序遍历」的遍历程序为 「左 - 根 - 右」。
能够依据传入节点 pNode 是否有「右儿子」，以及传入节点 pNode 是否为其「父节点」的「左儿子」来进行分状况探讨：
- 传入节点
pNode有「右儿子」：依据「中序遍历」的遍历程序为 「左 - 根 - 右」，能够确定「下一个节点」必然为以后节点的「右子树」中「最靠左的节点」； - 传入节点
pNode没有「右儿子」，这时候须要依据以后节点是否为其「父节点」的「左儿子」来进行分状况探讨： - 如果传入节点
pNode自身是其「父节点」的「左儿子」，那么依据「中序遍历」的遍历程序为为 「左 - 根 - 右」 可知，下一个节点正是该父节点，间接返回该节点即可； - 如果传入节点
pNode自身是其「父节点」的「右儿子」，那么依据「中序遍历」的遍历程序为为 「左 - 根 - 右」 可知，其父节点曾经被遍历过了，咱们须要递归找到合乎node.equals(node.next.left)的节点作为答案返回，如果没有则阐明以后节点是整颗二叉树最靠右的节点，这时候返回null即可。
代码：
| public class Solution {public TreeLinkNode GetNext(TreeLinkNode pNode) {if (pNode.right != null) { | |
| // 如果以后节点有右儿子，下一节点为以后节点「右子树中最靠左的节点」pNode = pNode.right; | |
| while (pNode.left != null) pNode = pNode.left; | |
| return pNode; | |
| } else { | |
| // 如果以后节点没有右儿子，则「往上找父节点」，直到呈现满足「其左儿子是以后节点」的父节点 | |
| while (pNode.next != null) {if (pNode.equals(pNode.next.left)) return pNode.next; | |
| pNode = pNode.next; | |
| } | |
| } | |
| return null; | |
| } | |
| } |
- 工夫复杂度：
- 空间复杂度：（看置顶评论）是 O(1)，不是
最初
这是咱们「剑指 の 精选」系列文章的第 No.57 篇，系列开始于 2021/07/01。
该系列会将牛客网「剑指 Offer」中比拟经典而又不过时的题目都讲一遍。
在提供谋求「证实」&「思路」的同时，提供最为简洁的代码。
欢送关注，交个敌人 (`・ ω ・´)
