难度: 中等 | 标签: 二叉搜索树 先序遍历

1. 题目描述

https://leetcode.cn/problems/serialize-and-deserialize-bst/
序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。

示例 1：
输入：root = [2,1,3]
输出：[2,1,3]
示例 2：
输入：root = []
输出：[]

提示：

  • 树中节点数范围是 [0, 104]
  • 0 <= Node.val <= 104
  • 题目数据 保证 输入的树是一棵二叉搜索树。

通过次数: 20,859 | 提交次数: 36,574

2. 题解

2022-05-11 AC

  1. serialize: 序列化就是深度搜索, 拿到先序遍历的val数组, 题目要求返回字符串, 就implode一下, 反正等下能解析出数组就行
  2. deserialize: 反序列化就是挨个往树中插入节点 ```php <?php /**
    • Created by PhpStorm
    • User: jtahstu
    • Time: 2022/5/11 0:10
    • Des: 449. 序列化和反序列化二叉搜索树
    • https://leetcode.cn/problems/serialize-and-deserialize-bst/
    • 设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。 */

//Definition for a binary tree node. class TreeNode { public $val = null; public $left = null; public $right = null;

  1. function __construct($value)
  2. {
  3.     $this->val = $value;
  4. }

}

class Codec { public $items = [];

function __construct()
{

}

/**
 * @param TreeNode $root
 * @return String
 */
function serialize($root)
{
    $this->dfs($root);
    return implode(',', $this->items);
}

function dfs($root)
{
    if ($root == null) {
        return;
    }

    $this->dfs($root->left);

    $this->dfs($root->right);
    $this->items[] = $root->val;
}

/**
 * @param String $data
 * @return TreeNode
 */
function deserialize($data)
{
    $items = explode(',', $data);
    if (!$items) {
        return new TreeNode(null);
    }
    $root = new TreeNode($items[0]);
    for ($i = 1; $i < count($items); $i++) {
        $this->insert($root, $items[$i]);
    }
    return $root;
}

function insert(&$root, $val)
{
    if ($val < $root->val) {
        if ($root->left == null) {
            $root->left = new TreeNode($val);
        } else {
            $this->insert($root->left, $val);
        }
    } else {
        if ($root->right == null) {
            $root->right = new TreeNode($val);
        } else {
            $this->insert($root->right, $val);
        }
    }
}

}

/**

  • Your Codec object will be instantiated and called as such:
  • $ser = new Codec();
  • $tree = $ser->serialize($param_1);
  • $deser = new Codec();
  • $ret = $deser->deserialize($tree);
  • return $ret; */

//object(TreeNode)#8 (3) { //[“val”]=> // string(1) “2” //[“left”]=> // object(TreeNode)#9 (3) { // [“val”]=> // string(1) “1” //[“left”]=> // NULL // [“right”]=> // NULL // } // [“right”]=> // object(TreeNode)#10 (3) { // [“val”]=> // string(1) “3” //[“left”]=> // NULL // [“right”]=> // NULL // } //}

/**

  • 执行用时：60 ms, 在所有 PHP 提交中击败了100.00%的用户
  • 内存消耗：27.7 MB, 在所有 PHP 提交中击败了100.00%的用户
  • 通过测试用例：62 / 62 */

$deser = new Codec(); $ret = $deser->deserialize(‘7,5,10,4,6,9,11’); $tree = $deser->serialize($ret); print_r($tree); print_r($ret); ```