Created
February 13, 2018 06:20
-
-
Save jianminchen/5ce3f22292c62b26f82dbf5b59486ed3 to your computer and use it in GitHub Desktop.
Leetcode 776 - binary search tree split tree by target value
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Diagnostics; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace BinarySearchTreeSplitTree | |
{ | |
/// <summary> | |
/// The algorith is written for my mock interview to test the candidate recursive solution. | |
/// Leetcode 776: Split binary search tree | |
/// </summary> | |
class Program | |
{ | |
internal class TreeNode | |
{ | |
public int Value { get; set; } | |
public TreeNode Left { get; set; } | |
public TreeNode Right { get; set; } | |
public TreeNode(int number) | |
{ | |
Value = number; | |
} | |
} | |
static void Main(string[] args) | |
{ | |
RunTestcase(); | |
} | |
public static void RunTestcase() | |
{ | |
// work on root node | |
var node20 = new TreeNode(20); | |
// work on level 1 | |
var node9 = new TreeNode(9); | |
var node25 = new TreeNode(25); | |
// work on connection from root node to its children | |
node20.Left = node9; | |
node20.Right = node25; | |
// work on level 2 | |
var node5 = new TreeNode(5); | |
var node12 = new TreeNode(12); | |
// work on connection from level 1's nodes to their children | |
node9.Left = node5; | |
node9.Right = node12; | |
// work on level 3 | |
var node11 = new TreeNode(11); | |
var node14 = new TreeNode(14); | |
// work on connection from level 2's nodes to their children | |
node12.Left = node11; | |
node12.Right = node14; | |
var successor1 = SplitTree(node20, 15); | |
var successor2 = SplitTree(node20, 9); | |
var successor3 = SplitTree(node20, 11); | |
} | |
/// <summary> | |
/// Split binary search tree | |
/// First tree with node value small and equal to the target value. | |
/// Second tree with node value greater than the target value. | |
/// </summary> | |
/// <param name="root"></param> | |
/// <param name="givenNode"></param> | |
/// <returns></returns> | |
public static TreeNode[] SplitTree(TreeNode root, int target) | |
{ | |
if (root == null) | |
{ | |
return new TreeNode[2]; | |
} | |
var splitLeftSubTree = root.Value > target; | |
if (splitLeftSubTree) | |
{ | |
var childTrees = SplitTree(root.Left, target); | |
var tmp = childTrees[1]; | |
childTrees[1] = root; | |
childTrees[1].Left = tmp; | |
return childTrees; | |
} | |
else | |
{ | |
var childTrees = SplitTree(root.Right, target); | |
var tmp = childTrees[0]; | |
childTrees[0] = root; | |
childTrees[0].Right = tmp; | |
return childTrees; | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment