110.平衡二叉樹(shù)

給定一個(gè)二叉樹(shù)棕洋，判斷它是否是高度平衡的二叉樹(shù)挡闰。

一棵高度平衡二叉樹(shù)定義為：
一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1 。

思路：自頂向下遞歸
在求二叉樹(shù)的高度基礎(chǔ)上掰盘，向上逐步判斷子樹(shù)是否高度差小于1摄悯。

    int height(TreeNode* root)//求二叉樹(shù)的高度
    {
        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);//分別求得左右子樹(shù)的高度
            int h_right=height(root->right);
            return (abs(h_left-h_right)<=1)&&isBalanced(root->left)&&isBalanced(root->right);
        }
    }

222.完全二叉樹(shù)

通用方法，沒(méi)體現(xiàn)出完全二叉樹(shù)特點(diǎn)

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

使用特征愧捕，算到倒數(shù)第二層

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

814. 二叉樹(shù)剪枝

給定二叉樹(shù)根結(jié)點(diǎn) root 奢驯，此外樹(shù)的每個(gè)結(jié)點(diǎn)的值要么是 0，要么是 1次绘。
返回移除了所有不包含 1 的子樹(shù)的原二叉樹(shù)瘪阁。
( 節(jié)點(diǎn) X 的子樹(shù)為 X 本身撒遣，以及所有 X 的后代。)
錯(cuò)誤代碼：

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(!root)
            return root;
        root->left=pruneTree(root->left);//左子樹(shù)剪枝
        root->right=pruneTree(root->right);//右子樹(shù)剪枝
        //根節(jié)點(diǎn)
        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;
        }
    }
};

錯(cuò)誤原因：沒(méi)找到遞歸的最后一層管跺。
正確代碼：

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(!root)
            return root;
        root->left=pruneTree(root->left);//左子樹(shù)剪枝
        root->right=pruneTree(root->right);//右子樹(shù)剪枝
        //根節(jié)點(diǎn)
        if(!root->left&&!root->right&&!root->val)
        {
            return nullptr;
        }
        return root;
    }
};

這道題可以歸結(jié)為遞歸子樹(shù)問(wèn)題义黎，求解時(shí)，先分別處理好左右子樹(shù)豁跑，然后處理根節(jié)點(diǎn)廉涕。
本題中，由于左右子樹(shù)已經(jīng)經(jīng)過(guò)剪枝處理艇拍，只需要判斷根節(jié)點(diǎn)是否需要剪枝狐蜕，即只需判定根節(jié)點(diǎn)及其左右子樹(shù)是否包含1。
由于左右子樹(shù)已經(jīng)經(jīng)過(guò)剪枝處理卸夕，可以判定层释，左右子樹(shù)一定包含1.所以如果左右子樹(shù)存在的話，根節(jié)點(diǎn)一定不用剪枝快集；如果左右子樹(shù)不存在湃累，而且根節(jié)點(diǎn)為0，此時(shí)需要剪掉根節(jié)點(diǎn)碍讨。