这道题和297非常像,不同的是这里不需要preorder 和inorder去重建binary tree, 因为bst的特点已经足够我们找到左右子树。

var serialize = function(root) {
    if (root === null) {
        return '';
    }
    const res = dfs(root);
    return res;
};

function dfs(root) {
    if (root === null) {
        return '';
    }
    if (root.left === null && root.right === null) {
        return String(root.val);
    }
    if (root.left === null) {
        return `${root.val},${dfs(root.right)}`;
    }
    if (root.right === null) {
        return `${root.val},${dfs(root.left)}`;
    }
    const left = dfs(root.left);
    const right = dfs(root.right);
    return `${root.val},${left},${right}`;
}

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    if (data === '') {
        return null;
    }
    const arr = data.split(',');
    return helper(arr);
};

function helper(arr) {
    if (arr.length === 0) {
        return null;
    }
    const curr = parseInt(arr[0]);
    let i = 1; 
    while (i < arr.length && arr[i] !== '' && parseInt(arr[i]) < curr) {
        i++;
    }
    const root = new TreeNode(curr);
    root.left = helper(arr.slice(1, i));
    root.right = helper(arr.slice(i));
    return root;
}

results matching ""

    No results matching ""