解决方案后序遍历前言二叉搜索树是一种特殊的二叉树序列化和反序列化过程也可以参照「297. 二叉树的序列化与反序列化」的过程。二叉搜索树的特殊之处在于其中序遍历是有序的可以利用这一点来优化时间和空间复杂度。思路给定一棵二叉树的「先序遍历」和「中序遍历」可以恢复这颗二叉树。给定一棵二叉树的「后序遍历」和「中序遍历」也可以恢复这颗二叉树。而对于二叉搜索树给定「先序遍历」或者「后序遍历」对其经过排序即可得到「中序遍历」。因此仅对二叉搜索树做「先序遍历」或者「后序遍历」即可达到序列化和反序列化的要求。此题解采用「后序遍历」的方法。序列化时只需要对二叉搜索树进行后序遍历再将数组编码成字符串即可。反序列化时需要先将字符串解码成后序遍历的数组。在将后序遍历的数组恢复成二叉搜索树时不需要先排序得到中序遍历的数组再根据中序和后序遍历的数组来恢复二叉树而可以根据有序性直接由后序遍历的数组恢复二叉搜索树。后序遍历得到的数组中根结点的值位于数组末尾左子树的节点均小于根节点的值右子树的节点均大于根节点的值可以根据这些性质设计递归函数恢复二叉搜索树。代码Python3class 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)Javapublic class Codec { public String serialize(TreeNode root) { ListInteger list new ArrayListInteger(); 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(, ); DequeInteger stack new ArrayDequeInteger(); 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, ListInteger list) { if (root null) { return; } postOrder(root.left, list); postOrder(root.right, list); list.add(root.val); } private TreeNode construct(int lower, int upper, DequeInteger 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; } }C#public class Codec { public string serialize(TreeNode root) { IListint list new Listint(); PostOrder(root, list); return string.Join(,, list); } public TreeNode deserialize(string data) { if (data.Length 0) { return null; } string[] arr data.Split(,); Stackint stack new Stackint(); int length arr.Length; for (int i 0; i length; i) { stack.Push(int.Parse(arr[i])); } return Construct(int.MinValue, int.MaxValue, stack); } private void PostOrder(TreeNode root, IListint list) { if (root null) { return; } PostOrder(root.left, list); PostOrder(root.right, list); list.Add(root.val); } private TreeNode Construct(int lower, int upper, Stackint stack) { if (stack.Count 0 || 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; } }
