Question

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

在这里插入图片描述

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/serialize-and-deserialize-bst/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Ideas

1、Answer( Java ) - 二叉搜索树（BST）后序遍历

解法思路：二叉搜索树（BST）后序遍历

在这里插入图片描述

👍后序遍历得到的数组中，根结点的值位于数组末尾，左子树的节点均小于根节点的值，右子树的节点均大于根节点的值，可以根据这些性质设计 递归函数 恢复二叉搜索树。
??注意事项：压栈顺序是 左右根，出栈顺序就是 根右左

Code

/**
 * @author Listen 1024
 * @description  449. 序列化和反序列化二叉搜索树（ 二叉搜索树（BST）特性 + 后序遍历 ）
 * 时间复杂度O(n)  其中 n 是树的节点数
 * 空间复杂度O(n)  其中 n 是树的节点数
 * @date 2022-05-11 8:47
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        postOrderSearch(root, list);
        String res = list.toString();
        return res.substring(1, res.length() - 1);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) {
            return null;
        }
        String[] strings = data.split(", ");
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < strings.length; i++) {
            stack.push(Integer.parseInt(strings[i]));
            //压栈顺序是左右根，出栈顺序就根右左
        }
        return reConstruct(Integer.MIN_VALUE, Integer.MAX_VALUE, stack);
    }


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

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

//部分题解参考链接(如侵删)
https://leetcode.cn/problems/serialize-and-deserialize-bst/solution/xu-lie-hua-he-fan-xu-lie-hua-er-cha-sou-5m9r4/
//图片来源(如侵删)
https://leetcode.cn/problems/serialize-and-deserialize-bst/solution/by-fuxuemingzhu-6vdj/