题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#
判断一棵二叉树是否为搜索二叉树和完全二叉树
http://www.nowcoder.com/practice/f31fc6d3caf24e7f8b4deb5cd9b5fa97
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root
* @return bool布尔型vector
*/
bool search_jug=true;
bool total_jug=true;
bool over=true;
int tall=0;
vector<bool> judgeIt(TreeNode* root) {
// write code here
vector<bool> ans;
TreeNode *node=root;
if(root==NULL){
ans.push_back(true);
ans.push_back(true);
return ans;
}
while(node->left!=NULL){
node=node->left;
tall=tall+1;
}
cout<<tall;
jugtree(root,0,INT_MAX,INT_MIN);
ans.push_back(search_jug);
ans.push_back(total_jug);
return ans;
}
void jugtree(TreeNode* node,int height,int max,int min){
if(node->val>=max||node->val<=min) search_jug=false;
if(height>tall) total_jug=false;
if(!(total_jug||search_jug)) return;
if(node->left!=NULL&&node->right!=NULL){
if(height==tall-1&&!over) total_jug=false;
jugtree(node->left,height+1,node->val,min);
jugtree(node->right,height+1,max,node->val);
}
else{
if(height==tall-1){
if(node->left==NULL&&node->right==NULL){
over=false;
}
else{
if(node->left!=NULL){
jugtree(node->left,height+1,node->val,min);
if(over) over=false;
else total_jug=false;
}
else{
jugtree(node->right,height+1,max,node->val);
total_jug=false;
}
}
}
else{
if(node->left==NULL&&node->right==NULL) return;
total_jug=false;
if(node->left!=NULL) jugtree(node->left,height+1,node->val,min);
else jugtree(node->right,height+1,max,node->val);
}
}
}
};
```jinxing
做出来了，记录一下，采用的就是深度遍历二叉树，对于完全二叉树和搜索二叉树分别进行不同的判断策略，搜索二叉树就是在遍历中对于子树设立一个max、min，即结点应该在的范围，并根据搜索二叉树的性质修改，若不满足则将search_jug改为false，而完全二叉树则首先while循环最左子树确定深度h，然后后续利用深度进行系列判断，关键是在当前深度为n-1时，若有一个节点不满足同时有左右结点，则记over为false，若只有右节点则直接total_jug为false，但若这个节点仍保持完全二叉树，若同高度下一节点又遇到over要改变，而此时over已经改为false，则直接改变total_jug，其他情况也需要全覆盖。
