《剑指Offer》-37.序列化二叉树

题干

请实现两个函数,分别用来序列化和反序列化二叉树。

解题思路

使用前序遍历,当碰到空指针时,使用特殊符号代替,节点之间使用符号分割。

代码实现

<?php

class TreeNode
{
    private $val;
    private $left;
    private $right;

    public function __set($name, $value)
    {
        $this->$name = $value;
    }

    public function __get($name)
    {
        return $this->$name;
    }
}

function getTree()
{
    $node1 = new TreeNode();
    $node1->val = 10;
    $node2 = new TreeNode();
    $node2->val = 6;
    $node3 = new TreeNode();
    $node3->val = 14;
    $node1->left = $node2;
    $node1->right = $node3;
    $node4 = new TreeNode();
    $node4->val = 4;
    $node5 = new TreeNode();
    $node5->val = 8;
    $node2->left = $node4;
    $node2->right = $node5;
    $node6 = new TreeNode();
    $node6->val = 12;
    $node7 = new TreeNode();
    $node7->val = 16;
    $node3->left = $node6;
    $node3->right = $node7;

    return $node1;
}

function serializeTree($root)
{
    if ($root == null) {
        echo '$,';

        return;
    }
    echo $root->val.',';
    serializeTree($root->left);
    serializeTree($root->right);
}

serializeTree(getTree());

function deserializeTree(&$root, &$serializeStr)
{
    if (($number = readChar($serializeStr))) {
        $node = new TreeNode();
        $node->val = $number;

        $root = $node;
        deserializeTree($left, $serializeStr);
        $root->left = $left;
        deserializeTree($right, $serializeStr);
        $root->right = $right;
    }
}

function readChar(&$serializeStr)
{
    if (empty($serializeStr)) {
        return false;
    }
    $tmp = explode(',', $serializeStr);
    $number = array_shift($tmp);
    if (!is_numeric($number)) {
        $number = false;
    }

    $serializeStr = implode(',', $tmp);

    return $number;
}
$root = null;
$str = '10,6,4,$,$,8,$,$,14,12,$,$,16,$,$,';
deserializeTree($root, $str);

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 树的概述 树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构 1.树的定...
    Jack921阅读 4,484评论 1 31
  • 前言 2. 实现 Singleton 3. 数组中重复的数字 4. 二维数组中的查找 5. 替换空格 6. 从尾到...
    Observer_____阅读 2,975评论 0 1
  • 一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这...
    Winterfell_Z阅读 5,925评论 0 13
  • 人到了一定年纪容易变得怀旧。每个人、每一代人都会有自己的专属记忆,一首歌,一部电影,一个场景,一个物件……都能把我...
    米布私人档案馆阅读 421评论 0 1
  • 晚上放学,和同学们一起吃饭,得到一个让大家振奋的消息。 其中一个同学在前一段突然之间有了一个开悟,给自己带来极大的...
    皮皮老猫阅读 201评论 0 0