判斷一棵二叉樹是否是二叉查找樹

來自專欄 演算法工程師面試題

二叉查找樹（英語：Binary Search Tree），也稱二叉搜索樹、有序二叉樹（英語：ordered binary tree），排序二叉樹（英語：sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：

1. 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
2. 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；
3. 任意節點的左、右子樹也分別為二叉查找樹；
4. 沒有鍵值相等的節點。

二叉查找樹相比於其他數據結構的優勢在於查找、插入的時間複雜度較低。為O(log n)

判斷一棵樹是不是BST樹方法：使用中序遍歷

1) 對樹進行中序遍歷，將結果保存在temp數組中。

3) 檢測temp數組中元素是否為升序排列。如果是，則這棵樹為BST.

時間複雜度: O(n)

還可以進一步的優化，我們可以避免使用這個額外的數組。在中序遍歷時，可以保存前驅節點，如果當前節點小於前驅節點，則這棵樹不是BST.

bool isBST(Node* root) { static Node *prev = NULL; // 中序遍歷這棵樹，並保存前驅節點至prev中 if (root) { if (!isBST(root->left)) return false; // 檢測節點值的合法性 if (prev != NULL && root->key <= prev->key) return false; prev = root; //右子樹 return isBST(root->right); } return true; }

推薦閱讀：