小白友好向

题目

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路

一开始没 get 到意思，关键函数只有一个参数 pNode 传入，数据结构如下所示：

/*function TreeLinkNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
    this.next = null;
}*/

结合原书描述和官方题解表述的意思，此处的 next 指向父节点，非下一节点指向

  • 暴力

    时间复杂度 O(n) ，空间复杂度 O(n)

    分析废物必备写法

    • 得出此时的中序遍历序列
    • 取传入节点的后一位

  • 分类处理

    分类容易分漏

    相比暴力，降低了空间复杂度到 O(1)

    官方题解中的分类方式为看图分析找不同，再归类

    私以为，此种办法小白比较容易遗漏，接着卡住，听取蛙声一片

    万能分类讨论法（梦回高中数学题）：

    咱从规则出发分类

    分到头了再对上图里的点验证一下有没有遗漏

    结果相似的看看是不是分类分繁了，可整理为：

    1. 中序遍历 => 左 中 右 => 从当前结点看，其属于中，故只讨论右子树的情况

    2. 有右子树

      中序遍历 => 左 中 右

      最先想到有左子树的情况，下一个为右子树的最左节点（中（左中右））

      没左子树的话，根据遍历规则，下一个为右子树的根节点 （中（- 中右））

      1. 右子树有左子树 => 结果：右子树最左节点（A, B, C, D）
      2. 右子树无左子树 => 结果：右子树自身节点（E, F, G）

    3. 无右子树

      中序遍历 => 左 中 右

      此时这部分小范围已经结束遍历了，结合遍历规则可得

      接下来得根据它相对其父节点的位置再分析，即：

      ​ 如为父的左子树，下一个就是父节点（中 -）中

      ​ 如为父的右子树，下一个就是第一个有未访问过右子树的父节点（（中 -）...） 中

      注意此块得循环判断，即某部分可能是某层的右子树，再上一层可能是左子树

      1. 当前结点为其父节点的左子树 => 结果：父节点 （I, L, N）
      1. 当前结点为其父节点的右子树 => 结果：第一个有未访问过右子树的父节点（H, J, K, M）

    img

    1. 最末尾元素 => 结果：null

    （示例图片源自牛客该题中的评论区）

    综上所述，总共为 5 种，分别为 ....

// 暴力
function GetNext(pNode)
{
  if(!pNode) return null;
  const stack = [];
  const res = [];
  let curr = pNode;
  // 取到根节点
  while(curr.next) {
    curr = curr.next;
  }
  // 中序遍历
  while(stack.length || curr) {
    while(curr) {
      stack.push(curr);
      curr = curr.left;
    }
    const node = stack.pop();
    // 题目中未声明数据不重复，故存整个节点
    res.push(node);
    if(node.right) {
      curr = node.right;
    }
  }
  // 遍历找下一值
  return res[res.indexOf(pNode) + 1];
}
// 分类 - 简化写法，两类再合并
function GetNext(pNode)
{
  if(!pNode) return null;
  if(pNode.right){
    // 1. 有右子树, 右子树有/无左子树
    // 结果：右子树最左节点（无左子树时，自身即为最左）
    pNode = pNode.right;
    while(pNode.left){
      pNode = pNode.left;
    }
    return pNode;
  }
  while(pNode.next){
    // 2. 无右子树，当前结点为其父节点的右/左子树
    // 结果：找第一个“当前节点”为左子树的父节点
    let pRoot = pNode.next;
    if(pNode === pRoot.left){
      return pRoot;
    }
    pNode = pNode.next;
  }
  // 3. 中序遍历最末节点
  return null;
}