#56 Coding面試 LeetCode #230. Kth Smallest Element in a BST

原文的題目網址在這

有好長一段時間沒有到 LeetCode 網站上去看題目了，今天去的時候才發現 LeetCode 網站做了一些小改變並且增加了更多的題目．不僅演算法類的題目增加，也新增了其他種類．如 OO 設計，系統設計等．真的是稱的上軟體工程師面試題目的最佳網站了．我以前在 LeetCode 上寫了很多題目，這網站有一個優點就是它會把你之前寫過的程式碼保留下來，所以我還能看到我之前寫的答案．

這一題是考找出 BST 中第 K 個最小值．要解決這題，有兩個先決條件．第一，你得知道什麼是 BST (binary search tree)，第二，你得知道第 K 個最小值是怎麼來的．基本上，如果遇到 TREE 這方面的題目都考 "特質"．因此，得先把每個 TREE 的最重要特質記在心裡．BST 最重要的特質就是，在任意一個 tree node 上，其左邊 node 的值比自己小，而右邊 node 的值比自己大．比如下面這邊小樹

5
    / \
   3   7

接著，怎麼找第 K 個最小值 ? 凡是遇到 tree 的題目要你比大小或是找第幾個這類跟順序有關的，一定要想到 tree traversal．Tree traversal 有三種，in-order, pre-order, 以及 post-order．其中 in-order 的走法用在 BST 上時，把樹走完後，拜訪的順序剛好就會把值從小排到大．以上圖而例就是 3->5->7，因此想找第 K 個最小值剛好就等於 in-order 走法拜訪的第 K 個 tree node.

如果以上都沒問題的話，接著就直接寫程式了．Tree 的拜訪我一向習慣用的是 iterative 的方法來寫．所以寫出來的程式如下:

	public int KthSmallest(TreeNode root, int k)
	{
	if (root == null) return 0;
	Stack stack = new Stack();
	TreeNode node = root;
	int count = 1;
	while (stack.Count & gt; 0 || node != null)
	{
	if (node != null)
	{
	stack.Push(node);
	node = node.left;
	}
	else
	{
	TreeNode t = stack.Pop();
	if (count == k) return t.val;
	node = t.right;
	count++;
	}
	}
	return 0;
	}

view raw LeetCode-230-1 hosted with ❤ by GitHub

如果你在面試時遇到這類的問題，我都會建議用 iterative 的寫法．這能避免使用 recursive，避免的原因就是在於當 tree 很大很大時, recursive 會造成 call stack overflow，這是做產品的公司所不能接收的大禁．

這是我以前的答案，使用 Stack 來記錄拜訪 BST 的走過痕跡．當我再重新 submit 到 LeetCode judge system 後，它告訴我上述的程式花了 189ms 跑完，在 C# 的答案裡面打敗了 41% 的答案．這表示有 59% 的答案效能跑的比這程式還快．看來這程式用了 Stack 果然還是有影響．為了追求更好的效能，把程式改成如下:

	int answer = 0;
	int count;
	int target;
	public int KthSmallest(TreeNode root, int k)
	{
	if (root == null) return 0;
	count = 0;
	target = k;
	recursiveInorder(root);
	return answer;
	}
	public void recursiveInorder(TreeNode root)
	{
	if (root.left != null)
	{
	recursiveInorder(root.left);
	}
	count++;
	if (count == target)
	{
	answer = root.val;
	return;
	}
	if (root.right != null)
	{
	recursiveInorder(root.right);
	}
	}

view raw LeetCode-230-2 hosted with ❤ by GitHub

再重新讓 LeetCode judge system 測驗後，這次它回傳此程式的效能打敗了 68% 的答案．顯然 32% 的答案有更快的效能，的確很利害．不過 LeetCode 這一題的 test case 中並沒有很大很大的樹，所以用 recursive 的寫法並沒有造成 stack overflow 的現象．