朴素解法

一个朴素的做法是，根据题目对于 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;
    }
}
  • 时间复杂度：由于这里只是普通的二叉树，最坏情况下会退化成「一直往右」链表结构。复杂度为
  • 空间复杂度：

最后

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

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

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

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

图片说明