解法一：中序遍历（递归）+ 层次遍历
一棵「二叉搜索树」需要满足要求：对于每个结点，左子树上的所有结点小于它，右子树上的所有结点大于它。
判断一棵二叉树是否为「二叉搜索树」的通用方法为：对该二叉树进行中序遍历，若遍历结果为「严格」单调递增的，则是一棵二叉搜索树，否则不是。
这是因为：中序遍历的步骤是：对于每个结点，先访问其「左子树」，再访问该结点，最后访问其「右子树」；而一棵二叉搜索树左子树结点必小于该结点、右子树上的结点必大于该结点，因此中序遍历的结果为严格单调递增。解法一通过「递归」的方式进行中序遍历，并维护了一个数组用以保存中序遍历的结果，遍历数组来判断是否为严格递增的。
判断一棵树是否为「完全二叉树」的方式为：对其进行层次遍历，若遇到一个空结点，则其后面的结点必须全为空结点，否则不是完全二叉树。具体思路如图所示。
图中，黄色结点为空结点，当遍历到「结点6出队列」后，此时队列中的所有元素必须全为空，否则不是一颗完全二叉树。
根据上述思路，实现的代码如下：
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return bool布尔型vector
*/
vector<bool> judgeIt(TreeNode* root) {
vector<bool> res(2, false);
if (!root) {
res[0] = false;
res[1] = false;
return res;
}
vector<int> inorderRes;
inorder(root, inorderRes); // 中序遍历
res[0] = true;
// 判断中序遍历结果是否升序
for (int i = 0; i < inorderRes.size() - 1; i ++) {
if (inorderRes[i] >= inorderRes[i + 1]) {
res[0] = false;
break;
}
}
// 层次遍历
res[1] = levelOrder(root);
return res;
}
void inorder(TreeNode* root, vector<int>& inorderRes) {
if (!root) return;
inorder(root->left, inorderRes); // 访问左子树
inorderRes.push_back(root->val); // 访问根结点
inorder(root->right, inorderRes); // 访问右子树
return;
}
bool levelOrder(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while (q.front()) {
TreeNode* tmp = q.front();
q.pop();
q.push(tmp->left);
q.push(tmp->right);
}
// 队列元素必须全为空
while (q.size() && !q.front()) {
q.pop();
}
return q.empty();
}
}; 该方法需要遍历两次树，因此时间复杂度为O(N)；该方法定义了数组和队列分别用来进行中序遍历和层次遍历，因此空间复杂度为O(N)。
解法二：中序遍历（非递归）+ 层次遍历优化
解法二给出了中序遍历的「非递归实现」，其实现思路如图所示。
步骤如下：
- 定义一个栈s，用来存储待访问的结点；
- 对每个结点（设为root），若其左孩子不为空，则将其入栈，并将root置于其左孩子的位置；
- 若其左孩子为空，则访问栈s的栈顶元素（记为t）、并出栈，并将root置为t的右孩子；
- 重复上述步骤，直至栈s为空且root为空指针。
对于层次遍历，可以优化解法一的两层while循环为一层循环：设标志位flag，若检测到当前结点为空，则置flag为true，若此时后续遇到非空结点，说明不是完全二叉树。
根据上述思路，实现的代码如下：
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return bool布尔型vector
*/
vector<bool> judgeIt(TreeNode* root) {
vector<bool> res(2);
if (!root) {
res[0] = false; res[1] = false;
return res;
}
// 定义栈 中序遍历
stack<TreeNode*> s;
TreeNode* p = root;
int min_ = INT_MIN;
res[0] = true;
while (p || s.size()) {
while (p) {
s.push(p);
p = p->left;
}
if (s.size()) {
p = s.top();
// 判断是否严格递增
if (min_ < p->val)
min_ = p->val;
else {
res[0] = false;
break;
}
s.pop();
p = p->right;
}
}
// 定义队列 层次遍历
queue<TreeNode*> q;
bool flag = false;
res[1] = true;
q.push(root);
while (q.size()) {
TreeNode* tmp = q.front();
q.pop();
// 遇到空结点 flag置为true
if (!tmp) {
flag = true;
continue;
} else {
// 遇到非空结点
if (flag) {
res[1] = false;
break;
} else { // flag仍为false时，继续遍历
q.push(tmp->left);
q.push(tmp->right);
}
}
}
return res;
}
}; 该方法需要遍历两次树，因此时间复杂度为O(N)；该方法定义了栈和队列分别用来进行中序遍历和层次遍历，因此空间复杂度为O(N)。
解法优化：优化中序遍历（递归）
对于解法一中的递归进行中序遍历，可以优化其空间复杂度，即无需定义数组保存结果。注意：此优化方法在递归时需要使用栈空间，空间复杂度为O(N)。
在每次递归时，比较当前元素是否在low到high所定义的范围内；若满足条件则进行下一次递归，否则直接返回false。
实现的代码如下：
bool inorder(TreeNode* root, int low, int high) {
if (!root)
return true;
// 不满足中序遍历递增要求
if (!(root->val > low && root->val < high))
return false;
// 分别递归左子树和右子树，同时更新low和high
return inorder(root->left, low, root->val) && inorder(root->right, root->val, high);
} 在调用该函数时，初始化low和high分别为INT_MIN和INT_MAX。
京公网安备 11010502036488号