Add solution for problem 449

BigEgg · BigEgg · commit f73d30f37d7e · 2020-10-14T16:27:59.000-07:00
diff --git a/LeetCode.Test/0401-0450/0449-SerializeAndDeserializeBST-Test.cs b/LeetCode.Test/0401-0450/0449-SerializeAndDeserializeBST-Test.cs
@@ -0,0 +1,28 @@
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+namespace LeetCode.Test
+{
+    [TestClass]
+    public class _0449_SerializeAndDeserializeBST_Test
+    {
+        [TestMethod]
+        public void SerializeAndDeserialize_1()
+        {
+            var root = TestHelper.GenerateTree(new int?[] { 2, 1, 3 });
+
+            var solution = new _0449_SerializeAndDeserializeBST();
+            var result = solution.serialize(root);
+            AssertHelper.AssertTree(new int?[] { 2, 1, 3 }, solution.deserialize(result));
+        }
+
+        [TestMethod]
+        public void SerializeAndDeserialize_2()
+        {
+            var root = TestHelper.GenerateTree(new int?[] { 2, 1, 3 });
+
+            var solution = new _0449_SerializeAndDeserializeBST();
+            var result = solution.serialize(null);
+            Assert.IsNull(solution.deserialize(result));
+        }
+    }
+}
diff --git a/LeetCode.Test/LeetCode.Test.csproj b/LeetCode.Test/LeetCode.Test.csproj
@@ -375,6 +375,7 @@
     <Compile Include="0401-0450\0445-AddTwoNumbersII-Test.cs" />
     <Compile Include="0401-0450\0447-NumberOfBoomerangs-Test.cs" />
     <Compile Include="0401-0450\0448-FindAllNumbersDisappearedInAnArray-Test.cs" />
+    <Compile Include="0401-0450\0449-SerializeAndDeserializeBST-Test.cs" />
     <Compile Include="0401-0450\0450-DeleteNodeInABST-Test.cs" />
     <Compile Include="0451-0500\0451-SortCharactersByFrequency-Test.cs" />
     <Compile Include="0451-0500\0452-MinimumNumberOfArrowsToBurstBalloons-Test.cs" />
diff --git a/LeetCode/0401-0450/0449-SerializeAndDeserializeBST.cs b/LeetCode/0401-0450/0449-SerializeAndDeserializeBST.cs
@@ -0,0 +1,74 @@
+//-----------------------------------------------------------------------------
+// Runtime: 112ms
+// Memory Usage: 30.2 MB
+// Link: https://leetcode.com/submissions/detail/406714064/
+//-----------------------------------------------------------------------------
+
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace LeetCode
+{
+    /**
+     * Definition for a binary tree node.
+     * public class TreeNode {
+     *     public int val;
+     *     public TreeNode left;
+     *     public TreeNode right;
+     *     public TreeNode(int x) { val = x; }
+     * }
+     */
+    public class _0449_SerializeAndDeserializeBST
+    {
+
+        // Encodes a tree to a single string.
+        public string serialize(TreeNode root)
+        {
+            var sb = PostOrder(root, new StringBuilder());
+            if (sb.Length > 0)
+                sb.Remove(sb.Length - 1, 1);
+
+            return sb.ToString();
+        }
+
+        // Decodes your encoded data to tree.
+        public TreeNode deserialize(string data)
+        {
+            if (string.IsNullOrEmpty(data)) return null;
+
+            var nums = data.Split().Select(n => int.Parse(n)).ToList();
+            return Helper(int.MinValue, int.MaxValue, nums);
+        }
+
+        private StringBuilder PostOrder(TreeNode root, StringBuilder sb)
+        {
+            if (root == null) return sb;
+            PostOrder(root.left, sb);
+            PostOrder(root.right, sb);
+            sb.Append(root.val);
+            sb.Append(" ");
+            return sb;
+        }
+
+        private TreeNode Helper(int lower, int upper, IList<int> nums)
+        {
+            if (nums.Count == 0) return null;
+            var value = nums.Last();
+            if (value < lower || value > upper) return null;
+
+            nums.RemoveAt(nums.Count - 1);
+            var root = new TreeNode(value);
+            root.right = Helper(value, upper, nums);
+            root.left = Helper(lower, value, nums);
+            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;
+}
diff --git a/LeetCode/LeetCode.csproj b/LeetCode/LeetCode.csproj
@@ -366,6 +366,7 @@
     <Compile Include="0401-0450\0445-AddTwoNumbersII.cs" />
     <Compile Include="0401-0450\0447-NumberOfBoomerangs.cs" />
     <Compile Include="0401-0450\0448-FindAllNumbersDisappearedInAnArray.cs" />
+    <Compile Include="0401-0450\0449-SerializeAndDeserializeBST.cs" />
     <Compile Include="0401-0450\0450-DeleteNodeInABST.cs" />
     <Compile Include="0451-0500\0451-SortCharactersByFrequency.cs" />
     <Compile Include="0451-0500\0452-MinimumNumberOfArrowsToBurstBalloons.cs" />
diff --git a/README.md b/README.md
@@ -1,5 +1,5 @@
 [![AppVeyor Build Status](https://img.shields.io/appveyor/build/bigegg/leetcode-cs?label=Windows%20Build%20Status&logo=AppVeyor&style=flat-square)](https://ci.appveyor.com/project/BigEgg/leetcode-cs)
-[![Solved Problems](https://img.shields.io/badge/Solved%20Problems-820-blue.svg?style=flat-square)](https://github.com/BigEggStudy/LeetCode-CS)
+[![Solved Problems](https://img.shields.io/badge/Solved%20Problems-821-blue.svg?style=flat-square)](https://github.com/BigEggStudy/LeetCode-CS)
 
 # LeetCode
 The C# solutions for LeetCode problems.
@@ -415,6 +415,7 @@ The C# solutions for LeetCode problems.
 | 445 | Add Two Numbers II | [C#](./LeetCode/0401-0450/0445-AddTwoNumbersII.cs)(108ms) | N(N) | O(1) | |
 | 447 | Number of Boomerangs | [C#](./LeetCode/0401-0450/0447-NumberOfBoomerangs.cs)(244ms) | O(N<sup>2</sup>) | O(N) | |
 | 448 | Find All Numbers Disappeared in an Array | [C#](./LeetCode/0401-0450/0448-FindAllNumbersDisappearedInAnArray.cs)(296ms) | O(N) | O(1) | |
+| 449 | Serialize and Deserialize BST | [C#](./LeetCode/0401-0450/0449-SerializeAndDeserializeBST.cs)(112ms) | O(N) | O(N) | |
 | 450 | Delete Node in a BST | [C#](./LeetCode/0401-0450/0450-DeleteNodeInABST.cs)(100ms) | O(logN) | O(logN) | |
 
 ### Problems 451-500
