前言

有一顆二叉搜索樹，在不創(chuàng)建任何新節(jié)點的條件下，如何將它轉換成一個排序的雙向鏈表？本文就跟大家分享下這個算法，歡迎各位感興趣的開發(fā)者閱讀本文。

思路分析

在二叉樹中，每個節(jié)點都有兩個指向子節(jié)點的指針。在雙向鏈表中，每個節(jié)點也有兩個指針，分別指向前一個節(jié)點和后一個節(jié)點。這兩種節(jié)點的結構很相似，二叉搜索樹是一種排序的數(shù)據(jù)結構，它的左子節(jié)點的值總是小于父節(jié)點的值，右子節(jié)點的值總是大于父節(jié)點的值。

那么，我們在將二叉搜索樹轉換為排序雙向鏈表時：

• 原先指向左子節(jié)點的指針，調(diào)整為鏈表中指向前一個節(jié)點的指針。
• 原先指向右子節(jié)點的指針，調(diào)整為鏈表中指向后一個節(jié)點的指針。

如何轉換

接下來，我們考慮下如何進行轉換。由于轉換后的鏈表是排好序的，我們可以中序遍歷樹中的每個節(jié)點，因為我們在文章實現(xiàn)二叉搜索樹-中序遍歷中，總結出了它的特點是按照從小到大的順序訪問每個節(jié)點。

我們用一個具體的例子來做進一步的分析，當我們執(zhí)行中序遍歷到根節(jié)點的時候，就可以把樹看成3部分（如下圖所示）：

• 值為10的節(jié)點
• 根節(jié)點值為6的左子樹
• 根節(jié)點值為14的右子樹

根據(jù)排序鏈表的定義，值為10的節(jié)點將和它的左子樹中的最大節(jié)點（值為8的節(jié)點）鏈接起來，同時它還將和右子樹中最小的節(jié)點（值為12的節(jié)點）鏈接起來，如下圖所示，將其拆成了根節(jié)點、左、右子樹，我們把左子樹與右子樹都轉換成雙向鏈表之后再和根節(jié)點鏈接起來，整顆二叉搜索樹也就轉成了排序雙向鏈表。

總結思路

按照中序遍歷的順序，當我們遍歷轉換到根節(jié)點（值為10的節(jié)點）時，它的左子樹已經(jīng)轉換成一個排序的鏈表了，并且處在鏈表中的最后一個節(jié)點時當前值最大的節(jié)點。我們把值為8的節(jié)點和根節(jié)點鏈接起來，此時鏈表中的最后一個節(jié)點就是10了。接著我們?nèi)ケ闅v轉換右子樹，并把根節(jié)點和右子樹中最小的節(jié)點鏈接起來。

分析到這里，相信大家已經(jīng)看出了左、右子樹節(jié)點轉換的過程跟遍歷的過程是一樣的，因此我們可以用遞歸來解決問題。

• 將左子樹構造成雙鏈表，并返回頭節(jié)點
• 定位至左子樹雙鏈表最后一個節(jié)點
• 如果左子樹鏈表不為空的話，將當前根節(jié)點追加到左子樹鏈表
• 將右子樹構造成雙鏈表，并返回頭節(jié)點
• 如果右子樹鏈表不為空的話，將該鏈表追加到root節(jié)點之后
• 根據(jù)左子樹鏈表是否為空確定返回的節(jié)點

實現(xiàn)代碼

思路捋清之后，接下來我們看下代碼的實現(xiàn)。

export function treeToLinkedList(
  root: BinaryTreeNode | null | undefined
): BinaryTreeNode | null {
  if (root == null) return null;
  if (root.left == null && root.right == null) return root;
  // 將左子樹構造成雙鏈表，返回鏈表的頭節(jié)點
  const leftTree = treeToLinkedList(root.left);
  // 遍歷左子樹雙鏈表，找到它右子樹的最后一個節(jié)點
  let pNode = leftTree;
  while (pNode != null && pNode.right != null) {
    pNode = pNode.right;
  }
  // 最后一個節(jié)點存在，則將兩個節(jié)點相互連接起來
  if (pNode) {
    // 將其右子樹與根節(jié)點連接
    pNode.right = root;
    // 將根節(jié)點的左子樹與其連接
    root.left = pNode;
  }
  // 將右子樹構造成雙鏈表，返回鏈表的頭節(jié)點
  const rightTree = treeToLinkedList(root.right);
  // 右子樹鏈表不為空，則將該鏈表追加到root節(jié)點之后
  if (rightTree != null) {
    rightTree.left = root;
    root.right = rightTree;
  }
  return leftTree != null ? leftTree : root;
}

測試用例

我們用文章中所列舉的例子來校驗下上述代碼能否正確解決問題。

const tree: BinaryTreeNode = {
  key: 10,
  left: {
    key: 6,
    left: {
      key: 4
    },
    right: {
      key: 8
    }
  },
  right: {
    key: 14,
    left: {
      key: 12
    },
    right: {
      key: 16
    }
  }
};

const linkedListResult = treeToLinkedList(tree);
console.log(linkedListResult);

執(zhí)行結果如下所示，正確的將樹左右指針所指向的節(jié)點進行了更改。

image-20221222165006886

示例代碼

本文用到的代碼完整版請移步：

• BinaryTreeToDoublyLinkedList.ts
• binaryTreeToDoublyLinkedList-test.ts