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)<=1)&&isBalanced(root->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<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. 二叉树剪枝

给定二叉树根结点 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，此时需要剪掉根节点。