https://leetcode.com/problems/increasing-order-search-tree/
Please review for performance
Given a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.
Constraints:
The number of nodes in the given tree will be between 1 and 100. Each node will have a unique integer value from 0 to 1000.
using System.Collections.Generic;
using GraphsQuestions;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace TreeQuestions
{
/// <summary>
/// https://leetcode.com/problems/increasing-order-search-tree/
/// </summary>
[TestClass]
public class IncreasingBstTest
{
[TestMethod]
public void ExampleTest()
{
// 5
// / \
// 3 6
// / \ \
// 2 4 8
// / / \
// 1 7 9
TreeNode root = new TreeNode(5);
root.left = new TreeNode(3);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.left.left.left = new TreeNode(1);
root.right = new TreeNode(6);
root.right.right = new TreeNode(8);
root.right.right.left = new TreeNode(7);
root.right.right.right = new TreeNode(9);
var forEach = new InOrderForEach();
root = forEach.IncreasingBST(root);
int res = 1;
var curr = root;
while (curr != null)
{
Assert.AreEqual(res, curr.val);
curr = curr.right;
res++;
}
}
}
}
public class InOrderForEach
{
public TreeNode IncreasingBST(TreeNode root)
{
if (root == null)
{
return null;
}
List<int> vals = new List<int>();
InOrder(root, vals);
var ans = new TreeNode(0);
TreeNode curr = ans;
foreach (var v in vals)
{
curr.right = new TreeNode(v);
curr = curr.right;
}
return ans.right;
}
private void InOrder(TreeNode root, List<int> vals)
{
if (root == null)
{
return;
}
InOrder(root.left, vals);
vals.Add(root.val);
InOrder(root.right, vals);
}
}
}