電腦科學 ^ IT人生 ^ 公益課程

#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;
        }

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





Share:

0 意見:

張貼留言