php 解法, 执行用时: 24 ms, 内存消耗: 24 MB, 提交时间: 2023-09-04 09:23:18

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */

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->items[] = $root->val;
        $this->dfs($root->left);
        $this->dfs($root->right);
    }

    /**
     * @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;
 */

javascript 解法, 执行用时: 84 ms, 内存消耗: 48.6 MB, 提交时间: 2022-12-04 13:43:16

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
    const list = [];

    const postOrder = (root, list) => {
        if (!root) {
            return;
        }
        postOrder(root.left, list);
        postOrder(root.right, list);
        list.push(root.val);
    }

    postOrder(root, list);
    const str = list.join(',');
    return str;
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    if (data.length === 0) {
        return null;
    }
    let arr = data.split(',');
    const length = arr.length;
    const stack = [];
    for (let i = 0; i < length; i++) {
        stack.push(parseInt(arr[i]));
    }

    const construct = (lower, upper, stack) => {
        if (stack.length === 0 || stack[stack.length - 1] < lower || stack[stack.length - 1] > upper) {
            return null;
        }
        const val = stack.pop();
        const root = new TreeNode(val);
        root.right = construct(val, upper, stack);
        root.left = construct(lower, val, stack);
        return root;
    }

    return construct(-Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, stack);
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

golang 解法, 执行用时: 4 ms, 内存消耗: 6.3 MB, 提交时间: 2022-12-04 13:42:39

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Codec struct{}

func Constructor() (_ Codec) { return }

func (Codec) serialize(root *TreeNode) string {
    arr := []string{}
    var postOrder func(*TreeNode)
    postOrder = func(node *TreeNode) {
        if node == nil {
            return
        }
        postOrder(node.Left)
        postOrder(node.Right)
        arr = append(arr, strconv.Itoa(node.Val))
    }
    postOrder(root)
    return strings.Join(arr, " ")
}

func (Codec) deserialize(data string) *TreeNode {
    if data == "" {
        return nil
    }
    arr := strings.Split(data, " ")
    var construct func(int, int) *TreeNode
    construct = func(lower, upper int) *TreeNode {
        if len(arr) == 0 {
            return nil
        }
        val, _ := strconv.Atoi(arr[len(arr)-1])
        if val < lower || val > upper {
            return nil
        }
        arr = arr[:len(arr)-1]
        return &TreeNode{Val: val, Right: construct(val, upper), Left: construct(lower, val)}
    }
    return construct(math.MinInt32, math.MaxInt32)
}


/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor()
 * deser := Constructor()
 * tree := ser.serialize(root)
 * ans := deser.deserialize(tree)
 * return ans
 */

java 解法, 执行用时: 12 ms, 内存消耗: 42 MB, 提交时间: 2022-12-04 13:42:24

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    public String serialize(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        postOrder(root, list);
        String str = list.toString();
        return str.substring(1, str.length() - 1);
    }

    public TreeNode deserialize(String data) {
        if (data.isEmpty()) {
            return null;
        }
        String[] arr = data.split(", ");
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            stack.push(Integer.parseInt(arr[i]));
        }
        return construct(Integer.MIN_VALUE, Integer.MAX_VALUE, stack);
    }

    private void postOrder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postOrder(root.left, list);
        postOrder(root.right, list);
        list.add(root.val);
    }

    private TreeNode construct(int lower, int upper, Deque<Integer> stack) {
        if (stack.isEmpty() || stack.peek() < lower || stack.peek() > upper) {
            return null;
        }
        int val = stack.pop();
        TreeNode root = new TreeNode(val);
        root.right = construct(val, upper, stack);
        root.left = construct(lower, val, stack);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;

python3 解法, 执行用时: 76 ms, 内存消耗: 19.2 MB, 提交时间: 2022-12-04 13:41:30

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:
    def serialize(self, root: TreeNode) -> str:
        arr = []
        def postOrder(root: TreeNode) -> None:
            if root is None:
                return
            postOrder(root.left)
            postOrder(root.right)
            arr.append(root.val)
        postOrder(root)
        return ' '.join(map(str, arr))

    def deserialize(self, data: str) -> TreeNode:
        arr = list(map(int, data.split()))
        def construct(lower: int, upper: int) -> TreeNode:
            if arr == [] or arr[-1] < lower or arr[-1] > upper:
                return None
            val = arr.pop()
            root = TreeNode(val)
            root.right = construct(val, upper)
            root.left = construct(lower, val)
            return root
        return construct(-inf, inf)
        

# Your Codec object will be instantiated and called as such:
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans