我記得這一題我被問過兩次，是兩個不同的團隊，而且都是跟資料庫有關的工作．所以，若你也要尋找資料庫相關的開發工作，看來 Tree 的題目是很難避免的．
這題的題目很單純，就是要寫一個 function 用來驗證題目的 Tree 是不是 Binary Search Tree (BST).
根據 BST 的定義，左邊的節點值必需小於父節點值，而右邊的節點值必需大於父節點值.
但這題有一點要小心的是，別只是檢查父節點值而己，應該要檢查所有上層的父節點值都要小於或是大於．
如果題目只給你 tree root，那麼你可以寫出像下面的 function 來檢查這個 tree 是不是 BST.
public bool IsValidBST(TreeNode root)
{
return BST(root, null, null);
}
bool BST(TreeNode node, int? min, int? max)
{
if (node == null) return true;
if (min == null && max == null)
{
return BST(node.left, min, node.val ) && BST(node.right, node.val , max);
}
else if (min != null && max == null)
{
if (node.val > min )
return BST(node.left, min, node.val) && BST(node.right, node.val, max);
}
else if (min == null && max !=null)
{
if ( node.val < max)
return BST(node.left, min, node.val) && BST(node.right, node.val, max);
}
else
{
if (node.val > min && node.val < max)
return BST(node.left, min, node.val) && BST(node.right, node.val, max);
}
return false;
}
若你仔細看的話，我是把每個分支出去時可能的節點值範圍也傳遞過去．這樣的寫法也許不是最好，但就如之前文章所說，要在五分鐘內想好然後在半小時內寫完再測試，所以就勉強用了.
這時候如果遇到要求更高的面試人員，他可能會說 recursive 的方法不適合用在 tree，所以要改成 iterative 的方式來寫．
其實要改成 iterative 的方式，說難不難，說簡單也不簡單，因為要在那短時間想出來也是件不容易的事．比較幸運的是之前我有練習過 BST 用 In-order traversal 的走法來驗證 BST，所以這題也就順利寫完了，以下就是改成 iterative 的方式，用 In-order 走訪 BST 之後，得到的答案一定是從小排到大的數值，所以只要多一個 for loop 來檢查數值是不是從小排到大即可.
public bool IsValidBST(TreeNode root)
{
if (root == null) return true;
List<int> re = InOrder(root);
if (re.Count == 1) return true;
for (int i = 0; i < re.Count - 1; i++)
{
if (re[i] >= re[i + 1])
return false;
}
return true;
}
List<int> InOrder(TreeNode node)
{
List<int> result = new List<int>();
Stack<TreeNode> stack = new Stack<TreeNode>();
while (stack.Count != 0 || node != null)
{
if (node != null)
{
stack.Push(node);
node = node.left;
}
else
{
TreeNode t = stack.Pop();
result.Add(t.val);
node = t.right;
}
}
return result;
}
雖然在初步面談中都把上述的題目做完了，但這也不代表就有機會可以繼續做後續的面試．所以，很可惜沒能做成資料庫開發的工作，找工作真的一切都是個緣份.
這題的題目很單純，就是要寫一個 function 用來驗證題目的 Tree 是不是 Binary Search Tree (BST).
根據 BST 的定義，左邊的節點值必需小於父節點值，而右邊的節點值必需大於父節點值.
但這題有一點要小心的是，別只是檢查父節點值而己，應該要檢查所有上層的父節點值都要小於或是大於．
如果題目只給你 tree root，那麼你可以寫出像下面的 function 來檢查這個 tree 是不是 BST.
public bool IsValidBST(TreeNode root)
{
return BST(root, null, null);
}
bool BST(TreeNode node, int? min, int? max)
{
if (node == null) return true;
if (min == null && max == null)
{
return BST(node.left, min, node.val ) && BST(node.right, node.val , max);
}
else if (min != null && max == null)
{
if (node.val > min )
return BST(node.left, min, node.val) && BST(node.right, node.val, max);
}
else if (min == null && max !=null)
{
if ( node.val < max)
return BST(node.left, min, node.val) && BST(node.right, node.val, max);
}
else
{
if (node.val > min && node.val < max)
return BST(node.left, min, node.val) && BST(node.right, node.val, max);
}
return false;
}
若你仔細看的話，我是把每個分支出去時可能的節點值範圍也傳遞過去．這樣的寫法也許不是最好，但就如之前文章所說，要在五分鐘內想好然後在半小時內寫完再測試，所以就勉強用了.
這時候如果遇到要求更高的面試人員，他可能會說 recursive 的方法不適合用在 tree，所以要改成 iterative 的方式來寫．
其實要改成 iterative 的方式，說難不難，說簡單也不簡單，因為要在那短時間想出來也是件不容易的事．比較幸運的是之前我有練習過 BST 用 In-order traversal 的走法來驗證 BST，所以這題也就順利寫完了，以下就是改成 iterative 的方式，用 In-order 走訪 BST 之後，得到的答案一定是從小排到大的數值，所以只要多一個 for loop 來檢查數值是不是從小排到大即可.
public bool IsValidBST(TreeNode root)
{
if (root == null) return true;
List<int> re = InOrder(root);
if (re.Count == 1) return true;
for (int i = 0; i < re.Count - 1; i++)
{
if (re[i] >= re[i + 1])
return false;
}
return true;
}
List<int> InOrder(TreeNode node)
{
List<int> result = new List<int>();
Stack<TreeNode> stack = new Stack<TreeNode>();
while (stack.Count != 0 || node != null)
{
if (node != null)
{
stack.Push(node);
node = node.left;
}
else
{
TreeNode t = stack.Pop();
result.Add(t.val);
node = t.right;
}
}
return result;
}
雖然在初步面談中都把上述的題目做完了，但這也不代表就有機會可以繼續做後續的面試．所以，很可惜沒能做成資料庫開發的工作，找工作真的一切都是個緣份.
