【剑指 の 精选】详解「二叉树中序遍历的下一个结点」两种解法（剑指offer）

【剑指 の 精选】详解「二叉树中序遍历的下一个结点」两种解法（剑指offer）

题目描述

这是「牛客网」上的「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​​ 是否存在「下一个节点」以及「下一节点」是哪一个。

Java 代码：

import java.util.*;public class Solution { List 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); }}

Python 3 代码：

class Solution: lt = [] def GetNext(self, pNode): # 根据传入的节点的 next 指针一直往上找，直到找到根节点 root root = pNode while root.next is not None: root = root.next # 对树进行一遍「中序遍历」，保存结果到 list 中 self.dfs(root) # 从 list 中找传入节点 pNode 的位置 idx n = len(self.lt) idx = -1 for i in range(n): if self.lt[i] == pNode: idx = i break # 如果 idx 不为「中序遍历」的最后一个元素，那么说明存在下一个节点，从 list 查找并返回 # 这里的 idx == -1 的判断属于防御性编程 return None if idx == -1 or idx == n -1 else self.lt[idx + 1] def dfs(self, root): if root is None: return self.dfs(root.left) self.lt.append(root) self.dfs(root.right)

时间复杂度：找头节点​​root​​​ 最多访问的节点数量不会超过树高 h；进行中序遍历的复杂度为 O(n)；从中序遍历结果中找到​​pNode​​ 的下一节点的复杂度为 O(n)。整体复杂度为 O(n)空间复杂度：忽略递归带来的额外空间消耗。复杂度为 O(n)

进阶解法

另外一个“进阶”的做法是充分利用「二叉树的中序遍历」来实现的。

我们知道，二叉树「中序遍历」的遍历顺序为 「左-根-右」。

可以根据传入节点 ​​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; }}

Python 3 代码：

class Solution: def GetNext(self, pNode): if pNode.right is not None: # 如果当前节点有右儿子，下一节点为当前节点「右子树中最靠左的节点」 pNode = pNode.right while pNode.left is not None: pNode = pNode.left return pNode else: # 如果当前节点没有右儿子，则「往上找父节点」，直到出现满足「其左儿子是当前节点」的父节点 while pNode.next is not None: if pNode == pNode.next.left: return pNode.next pNode = pNode.next return None

时间复杂度：O(n)空间复杂度：O(1)

最后

这是我们「剑指 の 精选」系列文章的第 ​​No.57​​ 篇，系列开始于 2021/07/01。

该系列会将牛客网「剑指 Offer」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。