LeetCode 449. 序列化和反序列化二叉搜索树

Categories:

题目描述
思路分析
1. 解法一：前序遍历 + 上下界复原（推荐）
相似题目

题目描述

✅ 449. 序列化和反序列化二叉搜索树

思路分析

解法一：前序遍历 + 上下界复原（推荐）

核心思路：

BST 前序序列具有“根在前、左子树值 < 根 < 右子树值”的性质。

序列化：直接输出前序遍历结果。

反序列化：用上下界限制递归构建左右子树。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(n)，用于递归栈与序列化结果。

class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        preorder(root, sb);
        if (sb.length() == 0) {
            return "";
        }
        sb.setLength(sb.length() - 1);
        return sb.toString();
    }

    private void preorder(TreeNode node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        sb.append(node.val).append(',');
        preorder(node.left, sb);
        preorder(node.right, sb);
    }

    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty()) {
            return null;
        }
        String[] parts = data.split(",");
        int[] idx = {0};
        return build(parts, idx, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private TreeNode build(String[] parts, int[] idx, long low, long high) {
        if (idx[0] == parts.length) {
            return null;
        }
        int val = Integer.parseInt(parts[idx[0]]);
        if (val <= low || val >= high) {
            return null;
        }
        idx[0]++;

        TreeNode node = new TreeNode(val);
        node.left = build(parts, idx, low, val);
        node.right = build(parts, idx, val, high);
        return node;
    }
}

import (
	"strconv"
	"strings"
)

type Codec struct{}

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

func (c *Codec) deserialize(data string) *TreeNode {
	if data == "" {
		return nil
	}
	parts := strings.Split(data, ",")
	idx := 0
	const lowBound int64 = -1 << 63
	const highBound int64 = 1<<63 - 1
	return buildBST(parts, &idx, lowBound, highBound)
}

func buildBST(parts []string, idx *int, low int64, high int64) *TreeNode {
	if *idx == len(parts) {
		return nil
	}
	val, _ := strconv.Atoi(parts[*idx])
	if int64(val) <= low || int64(val) >= high {
		return nil
	}
	*idx += 1

	node := &TreeNode{Val: val}
	node.Left = buildBST(parts, idx, low, int64(val))
	node.Right = buildBST(parts, idx, int64(val), high)
	return node
}

相似题目

题目	难度	考察点
449. 序列化和反序列化二叉搜索树	中等	递归
297. 二叉树的序列化与反序列化	困难	递归
1008. 前序遍历构造二叉搜索树	中等	递归
98. 验证二叉搜索树	中等	递归
235. 二叉搜索树的最近公共祖先	简单	递归
530. 二叉搜索树的最小绝对差	简单	递归

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/57808794