[코딩인터뷰] 문제 4.1

문제 4.1

Solutions.Library

	using Solutions.Library;
	#region Question 4.1
	// 주어진 이진 트리가 균형 이진 트리인지 판별하는 함수를 구현하라.
	// 이 문제에서 이진 트리는 어떤 노드의 두 자식 트리 깊이가 하나 이상 차이나지 않는 트리다.
	/// <summary>
	/// 변수 <paramref name="tree"/>이진 트리가 균형 이진 트리인지 판별한다.
	/// </summary>
	/// <param name="tree">균형을 검사할 이진 트리</param>
	/// <returns><paramref name="tree"/>이 균형이면 <code>true</code>를 반환한다.</returns>
	public static bool Q1_IsBalanced<T>(BinaryTree<T> tree)
	{
	if (CheckHeight(tree.Root) is null)
	{
	return false;
	}
	else
	{
	return true;
	}
	}
	/// <summary>
	/// 변수 <paramref name="node"/> 노드의 높이를 측정한다.
	/// </summary>
	/// <param name="node">높이를 검사할 이진트리 노드</param>
	/// <returns>노드의 높이를 반환한다. 다만, 균형이 깨졌을 경우 <code>null</code>을 반환한다.</returns>
	private static int? CheckHeight<T>(BinaryTreeNode<T> node)
	{
	if (node == null) { return 0; }
	var leftHeight = CheckHeight(node.Left);
	if (leftHeight == null) { return null; }
	var rightHeight = CheckHeight(node.Right);
	if (rightHeight == null) { return null; }
	var heightDiff = leftHeight - rightHeight;
	if (Math.Abs(heightDiff.GetValueOrDefault()) > 1) { return null; }
	else
	{
	return Math.Max(leftHeight.GetValueOrDefault(), rightHeight.GetValueOrDefault()) + 1;
	}
	}
	#endregion

view raw Code_Q4_1.cs hosted with ❤ by GitHub

	[TestMethod]
	public void Q4_1()
	{
	BinaryTree<int> tree;
	BinaryTreeNode<int> balanced = new BinaryTreeNode<int>(0)
	{
	Left = new BinaryTreeNode<int>(1)
	{
	Left = new BinaryTreeNode<int>(3)
	{
	Left = new BinaryTreeNode<int>(7),
	Right = new BinaryTreeNode<int>(8)
	},
	Right = new BinaryTreeNode<int>(4)
	{
	Left = new BinaryTreeNode<int>(9),
	Right = new BinaryTreeNode<int>(10)
	},
	},
	Right = new BinaryTreeNode<int>(2)
	{
	Left = new BinaryTreeNode<int>(5),
	Right = new BinaryTreeNode<int>(6)
	}
	};
	tree = new BinaryTree<int>(Comparer<int>.Default, balanced);
	Assert.IsTrue(TreeGraph.Q1_IsBalanced(tree));
	BinaryTreeNode<int> notBalanced = new BinaryTreeNode<int>(0)
	{
	Right = new BinaryTreeNode<int>(1)
	{
	Right = new BinaryTreeNode<int>(2)
	{
	Right = new BinaryTreeNode<int>(3)
	{
	Right = new BinaryTreeNode<int>(4),
	}
	}
	}
	};
	tree = new BinaryTree<int>(Comparer<int>.Default, notBalanced);
	Assert.IsFalse(TreeGraph.Q1_IsBalanced(tree));
	}

view raw Test_Q4_1.cs hosted with ❤ by GitHub