#27 Coding 面試 Leetcode #98 Validate Binary Search Tree

我記得這一題我被問過兩次，是兩個不同的團隊，而且都是跟資料庫有關的工作．所以，若你也要尋找資料庫相關的開發工作，看來 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;
        }

雖然在初步面談中都把上述的題目做完了，但這也不代表就有機會可以繼續做後續的面試．所以，很可惜沒能做成資料庫開發的工作，找工作真的一切都是個緣份.