题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#

判断一棵二叉树是否为搜索二叉树和完全二叉树

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 judge1(TreeNode* root,int &pre){ //判断是否为搜索二叉树
        //中序遍历
        if(root==NULL) return true;
        bool flag1=judge1(root->left,pre);
        bool flag2=root->val>pre;
        pre=root->val;
        bool flag3=judge1(root->right,pre);
        return flag1&&flag2&&flag3;
    }
    bool judge2(TreeNode* root){ //判断是否为完全二叉树
        if(root==NULL) return true;
        queue<TreeNode*> q;
        q.push(root);
        bool flag=false;
        while(!q.empty()){
            TreeNode* node=q.front();
            q.pop();
            if(flag&&(node->left||node->right)){//如果前面有缺少左儿子或者右儿子,但是该节点有儿子,返回false
                return false;
            }
            if(!node->left&&node->right) return false;  //如果二叉树节点有右儿子但是没有左儿子,直接返回false
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
            if(!node->left||!node->right) flag=true;
        }
        return true;
    }
    vector<bool> judgeIt(TreeNode* root) {
        // write code here
        vector<bool> ve(2,false);
        int pre=INT_MIN;
        ve[0]=judge1(root,pre);
        ve[1]=judge2(root);
        return ve;
    }
};
全部评论

相关推荐

风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
半解316:内容充实,细节需要修改一下。 1,整体压缩为一页。所有内容顶格。 2,项目描述删除,直接写个人工作量 修改完之后还需要建议,可以私聊
点赞 评论 收藏
分享
评论
2
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务