Created
November 20, 2018 01:56
-
-
Save jianminchen/33c26e851d623eb21f2b8c19affc7309 to your computer and use it in GitHub Desktop.
623 - add one row to tree - failed one test case, need to fix the bug -
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.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace _623_Add_one_row_to_tree | |
{ | |
public class TreeNode | |
{ | |
public int val; | |
public TreeNode left; | |
public TreeNode right; | |
public TreeNode(int x) { val = x; } | |
} | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
RunTestcase2(); | |
} | |
public static void RunTestcase() | |
{ | |
var node4 = new TreeNode(4); | |
var node2 = new TreeNode(2); | |
var node6 = new TreeNode(6); | |
var node3 = new TreeNode(3); | |
var node1 = new TreeNode(1); | |
var node5 = new TreeNode(5); | |
node4.left = node2; | |
node4.right = node6; | |
node2.left = node3; | |
node2.right = node1; | |
node6.left = node5; | |
var result = AddOneRow(node4, 1, 2); | |
} | |
public static void RunTestcase2() | |
{ | |
var node1 = new TreeNode(1); | |
var node2 = new TreeNode(2); | |
var node3 = new TreeNode(3); | |
var node4 = new TreeNode(4); | |
node1.left = node2; | |
node1.right = node3; | |
node2.left = node4; | |
var result = AddOneRow(node1, 5, 4); | |
} | |
/// <summary> | |
/// Add one row to tree at level specified by argument: level | |
/// the node's value is specified by argument: value | |
/// Tree's level starts from 1. | |
/// If level is 1, then add a new root, original root will be left | |
/// child of new root. | |
/// </summary> | |
/// <param name="root"></param> | |
/// <param name="value"></param> | |
/// <param name="level"></param> | |
/// <returns></returns> | |
public static TreeNode AddOneRow(TreeNode root, int value, int level) | |
{ | |
if (root == null || level < 1) | |
return null; | |
var dummyRoot = new TreeNode(-1); | |
dummyRoot.left = root; | |
var queue = new Queue<TreeNode>(); | |
queue.Enqueue(dummyRoot); | |
int index = 0; | |
while (queue.Count > 0) | |
{ | |
var levelCount = queue.Count; | |
for (int i = 0; i < levelCount; i++) | |
{ | |
var node = queue.Dequeue(); | |
var isRowToAdd = index == level - 1; | |
if (node.left != null) | |
{ | |
if(isRowToAdd) | |
{ | |
var tmp = node.left; | |
var added = new TreeNode(value); | |
node.left = added; | |
added.left = tmp; | |
queue.Enqueue(tmp); | |
} | |
else | |
{ | |
queue.Enqueue(node.left); | |
} | |
} | |
if (node.right != null) | |
{ | |
if (isRowToAdd) | |
{ | |
var tmp = node.right; | |
var added = new TreeNode(value); | |
node.right = added; | |
added.right = tmp; | |
queue.Enqueue(tmp); | |
} | |
else | |
{ | |
queue.Enqueue(node.right); | |
} | |
} | |
// catched by online judge - added row is empty row | |
if (isRowToAdd && node.left == null && node.right == null) | |
{ | |
node.left = new TreeNode(value); | |
node.right = new TreeNode(value); | |
} | |
} | |
index++; | |
} | |
return dummyRoot.left; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment