JavaScript：leetcode_1028. 從先序周遊還原二叉樹

題目說明

我們從二叉樹的根節點 root 開始進行深度優先搜尋。

在周遊中的每個節點處，我們輸出 D 條短劃線（其中 D 是該節點的深度），然後輸出該節點的值。（如果節點的深度為 D，則其直接子節點的深度為 D + 1。根節點的深度為 0）。

如果節點隻有一個子節點，那麼保證該子節點為左子節點。

給出周遊輸出 S，還原樹并傳回其根節點 root。

 

示例 1：



輸入："1-2--3--4-5--6--7"
輸出：[1,2,5,3,4,6,7]
示例 2：



輸入："1-2--3---4-5--6---7"
輸出：[1,2,5,3,null,6,null,4,null,7]
示例 3：



輸入："1-401--349---90--88"
輸出：[1,401,null,349,88,90]
 

提示：

原始樹中的節點數介于 1 和 1000 之間。
每個節點的值介于 1 和 10 ^ 9 之間。
           

解題思路一（S轉換數組，前序特性分割遞歸）

1. 這道題是困難題，但是其實對二叉樹稍微熟悉點的話，并不是很難，隻能說麻煩一些，一共分兩步，第一步處理字元串，第二步建構二叉樹。
2. 第一步首先将

   "1-401--349---90--88"

   轉換成一個同順序的節點數組

   arr

   ，這樣便于我們操作。
3. 第二步建構二叉樹
   1. 首先選擇根節點，也就是

      arr

      的第一位,其

      level

      為 。
   2. 然後在

      arr.slice(1)

      中尋找

      level

      為

      1

      的節點，也就是

      root

      的

      left

      和

      right

      節點。
   3. 注意題目說明：如果節點隻有一個子節點，那麼保證該子節點為左子節點。
   4. 也就是說我們按順序周遊

      arr

      ，第一個

      level

      為

      1

      的就是

      root

      的

      left

      節點，第二個就是

      right

      節點（最多兩個）
   5. 當找到

      left

      節點時，聲明

      left

      變量記錄下标

      i

      ，

      right

      節點同樣記錄下标，搜尋完畢之後

      level++

   6. [left+1，right)

      為左樹節點數組，

      [right + 1，arr.length)

      為右樹節點，分割遞歸。
   7. 然後判讀root.left 是否存在，若存在

      root.left && build(root.left, arr.slice(left + 1, right), level);

   8. 然後判讀root.right 是否存在，若存在

      root.right && build(root.right , arr.slice(right + 1), level);

   9. 當數組為空時傳回。
4. 傳回root

代碼實作一

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {string} S
 * @return {TreeNode}
 */
var recoverFromPreorder = function(S) {
    let levelFlag = 0;
    let arr = [];
    let num = '';
    for (let i = 0; i < S.length; i++) {
        if (S[i] === '-') {
            levelFlag++;
        } else {
            num += S[i];
            if (S[i + 1] == '-' || (i + 1) == S.length) {
                let node = new TreeNode(num);
                node.level = levelFlag;
                arr.push(node)
                levelFlag = 0;
                num = '';
            }
        }
    }
    let root = arr[0];
    build(root, arr.slice(1), 1);
    return root;
};

var build = function(root, arr, level) {
    if (!arr.length) {
        return;
    }
    let left = 0;
    let right = arr.length;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i].level === level) {
            if (root.left == null) {
                root.left = arr[i];
                left = i;
            } else {
                root.right = arr[i];
                right = i;
                break;
            }
        }
    }
    level++;
    root.left && build(root.left, arr.slice(left + 1, right), level);
    root.right && build(root.right, arr.slice(right + 1), level);
}