二叉树2-平衡二叉树、完全二叉树、二叉树剪枝

时间:2021-7-3 作者:qvyue

110.平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。

一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

思路:自顶向下递归
在求二叉树的高度基础上,向上逐步判断子树是否高度差小于1。

    int height(TreeNode* root)//求二叉树的高度
    {
        if(!root)
            return 0;
        return max(height(root->left),height(root->right))+1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root)
            return true;
        else{
            int h_left=height(root->left);//分别求得左右子树的高度
            int h_right=height(root->right);
            return (abs(h_left-h_right)left)&&isBalanced(root->right);
        }
    }

222.完全二叉树

通用方法,没体现出完全二叉树特点

return countNodes(root->left) + countNodes(root->right) + 1;

使用特征,算到倒数第二层

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root)
            return 0;
        queue q;
        int n=0;
        q.push(root);
        while(!q.empty())
        {
            int l=q.size();
            for(int i=0;ileft&&!tmp->right)
                    return n*2-1;
                else if(!tmp->right)
                    return n*2;
                q.push(tmp->left);
                q.push(tmp->right);
            }
        }
        return n;
    }
};

814. 二叉树剪枝

给定二叉树根结点 root ,此外树的每个结点的值要么是 0,要么是 1。
返回移除了所有不包含 1 的子树的原二叉树。
( 节点 X 的子树为 X 本身,以及所有 X 的后代。)
错误代码:

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(!root)
            return root;
        root->left=pruneTree(root->left);//左子树剪枝
        root->right=pruneTree(root->right);//右子树剪枝
        //根节点
        if(!root->left&&!root->right)
        {
            if(root->val==0)
            return nullptr;
            else
            return root;
        }
        else if(!root->left)
        {
            if(root->val+root->right->val==0)
            root->right=nullptr;
            return root; 
        }
        else if(!root->right)
        {
            if(root->val+root->left->val==0)
            root->left=nullptr;
            return root;
        }
        else{
            if(root->val+root->right->val+root->left->val==0)
            root=nullptr;
            return root;
        }
    }
};

错误原因:没找到递归的最后一层。
正确代码:

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(!root)
            return root;
        root->left=pruneTree(root->left);//左子树剪枝
        root->right=pruneTree(root->right);//右子树剪枝
        //根节点
        if(!root->left&&!root->right&&!root->val)
        {
            return nullptr;
        }
        return root;
    }
};

这道题可以归结为递归子树问题,求解时,先分别处理好左右子树,然后处理根节点。
本题中,由于左右子树已经经过剪枝处理,只需要判断根节点是否需要剪枝,即只需判定根节点及其左右子树是否包含1。
由于左右子树已经经过剪枝处理,可以判定,左右子树一定包含1.所以如果左右子树存在的话,根节点一定不用剪枝;如果左右子树不存在,而且根节点为0,此时需要剪掉根节点。

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。