扯皮

好久没写过小短文了，上班之后匀给写文章的时间非常少，通常都是碎片化时间稍微写几段，现在草稿箱里已经压了四篇文章没发了，这段时间赶紧整理一下

看到这个标题第一时间相信想到的都是 React 的 Fiber 架构，明明已经有很多篇文章解析了为什么还要写这个相关的呢？因为之前看了不少比较优秀的文章，有些会把虚拟 DOM 转 Fiber 链表的过程也进行详解，但是由于 Fiber 架构本身比较复杂，针对于这个过程并不会重点讲

这就导致一个问题，每次看完这部分内容后，只能说懂了没懂，突然有一天自己总结 Fiber 架构的时候上来先反问自己：虚拟 DOM 转 Fiber 的过程是怎样的呢？答：emm 先这样遍历一下，然后再那样，然后就成链表了...

说明还是不太懂，突然一想这不就是一个手写题么，以前树 -> 数组、数组 -> 树写的贼 6，到这个直接抓瞎了，赶紧下来总结一下

正文确定数据类型

既然是两个数据结构的转换那必然需要先确定这两个结构类型，树结构不多说了，既然链表能够描述一棵树，那它不是普通的链表，它是一个有功的三向链表，具体是哪三向呢？肯定就还是按照 React 的 fiber 来啦：

废话不多说，上 TS 写类型：

type TreeNodeType = {
  id: number;
  name: string;
  children?: TreeNodeType[];
};
type LinkNodeType = TreeNodeType;
class LinkNode {
  node: LinkNodeType | null;
  return: LinkNode | null = null;
  child: LinkNode | null = null;
  sibling: LinkNode | null = null;
  constructor(node?: LinkNodeType) {
    this.node = node || null;
  }
}

遍历顺序

要对树结构进行转化肯定要遍历每个树节点，我们肯定是需要一边遍历一边建立链表节点关系，关键在于是选 BFS 还是 DFS，不妨代入分析一下看看，以下面这棵树为例:

如果是 BFS 它的遍历顺序为：ABCDEFG

层序遍历上来就可以被抬走了，可以清楚的看到比较方便建立兄弟关系（sibling），毕竟都是一层紧挨着的，但是针对于父子关系（return、child）就错乱了，C -> D 明显关系错位

要想跟父子打好关系还是得靠 DFS ，DFS 又分为三种：ABDECFG（先序）、DBEAFCG（中序）、DEBFGCA（后序）还是考虑我们 return、sibling、child 的关系，以 B、D、E 三个节点为例，中序的 DBE （D、E sibling 关系）和后序的 DEB（父子关系）处理起来都不太方便

只有先序的 BDE 比较符合，但是又不完全一样，因为我们并不是先一路遍历到最底的节点再向上回头，而是先处理父节点，之后紧接着遍历处理孩子节点

先序遍历的 BDE 的顺序是符合的，但是针对于子树 ABC 不合适，一般情况下我们手写的 DFS 都是以递归的方式实现的，但在这里不只要遍历节点还要建立关系，通过这层关系能够让我们以循环的方式来实现

代码实现

根据上面的这棵二叉树来想想遍历过程中该怎么建立关系，不妨将整个二叉树拆成一棵棵子树，那么我们每轮其实就是在处理一个父节点和几个子节点之间的关系，我们先来棵只有父子关系的子树：

const tree: TreeNodeType = {
  id: 1,
  name: "A",
  children: [
    {
      id: 2,
      name: "B",
    },
    {
      id: 3,
      name: "C",
    },
    {
      id: 4,
      name: "D",
    },
    {
      id: 5,
      name: "E",
    },
  ],
};

来实现一个 handleTreeChildren 来建立关系，按照 Fiber 之间的关系其 child 指向是第一个孩子节点，所以其关键在于区分处理第一个孩子节点和其余孩子节点，其余孩子节点只需要在其之间建立 sibling 关系即可：

function handleTreeChildren(treeNode: TreeNodeType, children: TreeNodeType[]) {
  const headNode = new LinkNode(treeNode);
  let prevNode: LinkNode | null = null;
  children.forEach((node, index) => {
    const linkNode = new LinkNode(node);
    linkNode.return = headNode;
    if (index === 0) {
      headNode.child = linkNode;
    } else {
      prevNode!.sibling = linkNode;
    }
    prevNode = linkNode;
  });
  return headNode;
}
console.log(handleTreeChildren(tree, tree.children || []));

打印看下结果没什么毛病：

现在只是处理了一棵子树，后面要把子树串联起来，实际就是循环上面的子树处理过程，关键是怎么循环呢，需要回想一下 React Fiber 的处理过程，它的顺序是 child -> sibling -> return，也就是说我们处理完孩子节点后，需要再将 child 指向的第一个子节点重复上述过程，没有 child 就找 sibling，没有 sibling 就 return 回去找它的 sibling（俗称找叔叔‍♂️），我们来拓展 handleTreeChildren 的实现：

function handleTreeChildren(treeNode: TreeNodeType, children: TreeNodeType[]) {
  const headNode = new LinkNode(treeNode);
  let prevNode: LinkNode | null = null;
  children.forEach((node, index) => {
    const linkNode = new LinkNode(node);
    linkNode.return = headNode;
    if (index === 0) {
      headNode.child = linkNode;
    } else {
      prevNode!.sibling = linkNode;
    }
    prevNode = linkNode;
  });
  // new
  if (headNode.child) return headNode.child;
  if (headNode.sibling) return headNode.sibling;
  return headNode.return?.sibling;
}

除此之外就需要一个循环重复上述过程了，我们将 handleTreeChildren 中创建的 headNode 抽离至外面，以 while 循环的方式处理每棵子树:

// new
function TreeToLinkList(tree: TreeNodeType) {
  const headNode = new LinkNode(tree);
  let currentNode: LinkNode | null | undefined = headNode;
  while (currentNode) {
    const children = currentNode.node?.children || [];
    currentNode = handleTreeChildren(currentNode, children);
  }
  return headNode;
}
function handleTreeChildren(headNode: LinkNode, children: TreeNodeType[]) {
  let prevNode: LinkNode | null = null;
  children.forEach((node, index) => {
    const linkNode = new LinkNode(node);
    linkNode.return = headNode;
    if (index === 0) {
      headNode.child = linkNode;
    } else {
      prevNode!.sibling = linkNode;
    }
    prevNode = linkNode;
  });
  if (headNode.child) return headNode.child;
  if (headNode.sibling) return headNode.sibling;
  return headNode.return?.sibling;
}

用上面图中的那棵二叉树来看看结果，没什么问题：

const tree: TreeNodeType = {
  id: 1,
  name: "A",
  children: [
    {
      id: 2,
      name: "B",
      children: [
        {
          id: 4,
          name: "D",
        },
        {
          id: 5,
          name: "E",
        },
      ],
    },
    {
      id: 3,
      name: "C",
      children: [
        {
          id: 6,
          name: "F",
        },
        {
          id: 7,
          name: "G",
        },
      ],
    },
  ],
};
console.log(TreeToLinkList(tree));

到此我们树转链表的实现基本就结束啦，还有个特殊情况，真实场景下这里的树结构通常不是一个对象，而是一个数组结构里面存每个子树，需要针对于这种情况进行处理

思路其实很简单，我们可以手动创建一个带头链表，这个头节点不存数据只起链接作用，不过每次节点的 children 就需要我们手动存一下了，毕竟现在多了个带头节点，会与之前的实现错位：

function TreeToLinkList(tree: TreeNodeType | TreeNodeType[]) {
  // new
  const trees = Array.isArray(tree) ? tree : [tree];
  const headNode = new LinkNode();
  let currentNode: LinkNode | null | undefined = headNode;
  let treeChildren = trees;
  while (currentNode) {
    currentNode = handleTreeChildren(currentNode, treeChildren || []);
    treeChildren = currentNode?.node?.children || [];
  }
  // new
  return headNode.node ? headNode : headNode.child;
}

再来棵树看看效果，没什么问题，这其实也是 React 和 Vue 要求组件必须有一个根节点的原因，哪怕没有根节点框架底层也会给你包一层形成树结构而非数组：

const tree: TreeNodeType[] = [
  {
    id: 1,
    name: "A",
    children: [
      {
        id: 4,
        name: "D",
      },
      {
        id: 5,
        name: "E",
      },
    ],
  },
  {
    id: 2,
    name: "B",
  },
  {
    id: 3,
    name: "C",
    children: [
      {
        id: 6,
        name: "F",
      },
      {
        id: 7,
        name: "G",
      },
    ],
  },
];
console.log(TreeToLinkList(tree));

End

全部代码如下，除去类型的话感觉 40 行不到 ，整个实现过程就已经有 React 的影子了，像 while 循环再拓展一个条件就是时间分片，根据剩余时间来执行下次循环，也正是因为采取了这种结构才能够实现 React 所说的“中断”效果：

type TreeNodeType = {
  id: number;
  name: string;
  children?: TreeNodeType[];
};
type LinkNodeType = TreeNodeType;
class LinkNode {
  node: LinkNodeType | null;
  return: LinkNode | null = null;
  child: LinkNode | null = null;
  sibling: LinkNode | null = null;
  constructor(node?: LinkNodeType) {
    this.node = node || null;
  }
}
function TreeToLinkList(tree: TreeNodeType | TreeNodeType[]) {
  const trees = Array.isArray(tree) ? tree : [tree];
  const headNode = new LinkNode();
  let currentNode: LinkNode | null | undefined = headNode;
  let treeChildren = trees;
  while (currentNode) {
    currentNode = handleTreeChildren(currentNode, treeChildren || []);
    treeChildren = currentNode?.node?.children || [];
  }
  return headNode.node ? headNode : headNode.child;
}
function handleTreeChildren(headNode: LinkNode, children: TreeNodeType[]) {
  let prevNode: LinkNode | null = null;
  children.forEach((node, index) => {
    const linkNode = new LinkNode(node);
    linkNode.return = headNode;
    if (index === 0) {
      headNode.child = linkNode;
    } else {
      prevNode!.sibling = linkNode;
    }
    prevNode = linkNode;
  });
  if (headNode.child) return headNode.child;
  if (headNode.sibling) return headNode.sibling;
  return headNode.return?.sibling;
}

到此这篇小短文就结束了，别看实现的代码量不多，如果真让面试手写的话之前没有了解过 Fiber 架构还真不好撕出来，以后真能当上面试官了就搞点这些题来玩玩，代码量少不需要多长时间，还又考察了数据结构，多好的一道题