题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#
判断一棵二叉树是否为搜索二叉树和完全二叉树
https://www.nowcoder.com/practice/f31fc6d3caf24e7f8b4deb5cd9b5fa97
思路如下:判断是否是搜索树使用了递归而不是中序遍历的思路。判断是否是完全二叉树简单的用个层序遍历即可。
bool IsSearchTree(TreeNode* root,int min,int max) { if(root==NULL) return true; if(root->val<min || root->val >max) return false; //左子树中所有值都要严格小于根节点,因此左子树中所有数能达到的最大值也就 //必须都要小于根节点了。因此在递归左子树时最小值不变,最大值更新为根节 //点的值。右子树的递归也是同理。 return (IsSearchTree(root->left,min,root->val) && IsSearchTree(root->right, root->val, max)); } bool IsComplete(TreeNode* root) { if(root==NULL) return true; queue<TreeNode*> BQueue; BQueue.push(root); while(!BQueue.empty()) { TreeNode* Current=BQueue.front(); BQueue.pop(); if(Current->right && (!Current->left)) { return false; } else if(Current->left && Current->right) { BQueue.push(Current->left); BQueue.push(Current->right); } else//只有左节点,亦或是左右节点都没有。说明此时只剩下叶子节点了。 { while(!BQueue.empty()) { Current=BQueue.front(); BQueue.pop(); if(Current->left || Current->right) return false; } break; } } return true; } vector<bool> judgeIt(TreeNode* root) { // write code here vector<bool>result; if(root==NULL) { result.push_back(true); result.push_back(true); return result; } result.push_back(IsSearchTree(root,INT_MIN,INT_MAX)); result.push_back(IsComplete(root)); return result; }