C++刷题笔记(21)——leetcode222、110、257

与之前求二叉树深度的解法类似，不过把深度换成了节点数

class Solution {
public:
    int getnodenum(TreeNode* node) {
        if (node == NULL) return 0;
        int leftnum = getnodenum(node->left);     //左
        int rightnum = getnodenum(node->right);   //右
        return 1 + leftnum + rightnum;            //中
    }
    int countNodes(TreeNode* root) {
        getnodenum(root);
        //也可以精简成：return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

迭代法也是一样，将层数改为节点数

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == NULL) return 0;
        queue que;
        que.push(root);
        int num = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                num++;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return num;
    }
};

根据完全二叉树的定义，有两种可能，即要么是满二叉树、要么是最后一层节点不满

对于满二叉树可以利用其性质2^h-1计算，对于非满二叉树，可变遍历其左右孩子，直到某一深度的左右孩子为满二叉树

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftHeight = 0, rightHeight = 0; // 初始为0为了下面求指数方便
        while (left) {               // 求左子树深度
            left = left->left;
            leftHeight++;
        }
        while (right) {              // 求右子树深度
            right = right->right;
            rightHeight++;
        }
        if (leftHeight == rightHeight) {
            return (2 << leftHeight) - 1; // 注意(2<<1) 相当于2^2，所以leftHeight初始为0
        }
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

要注意二叉树高度和深度的定义
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

在leetcode上根节点的深度为1

根据定义，如果一棵树是平衡二叉树，那么它的所有子树都是平衡二叉树。

求深度一般用前序遍历（中左右）；
求高度一般用后序遍历（左右中）。

自顶向下的递归(前序遍历)：
对于当前遍历到的节点，首先计算左右子树的高度；
如果高度差不大于1，再分别递归的遍历左右子节点，判断左右子树是否平衡。

class Solution {
public:
    int getheight(TreeNode* node) {
        if (node == NULL) return 0;    //遇到空节点终止，当前节点为根节点的树高度为0
        else return 1 + max(getheight(node->left), getheight(node->right));  //获取一个节点的最大高度
    }
    bool isBalanced(TreeNode* root) {
        if (root == NULL) return true;   //如果根节点为0，则高度差不超过1，为平衡二叉树
        //当一个节点的左右子树高度差不超过1 且 该节点的左子树的左右子树高度差不超过1 且 该节点的右子树的左右子树高度差不超多1 返回真，否则返回假
        else return abs(getheight(root->left) - getheight(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
};

这种写法，时间复杂度很高，从最后返回的结果就能看出来

自低向上的递归(后续遍历)
对于当前遍历到的节点，先递归的判断其左右子树是否平衡，再判断以当前节点为根节点的子树是否平衡。

class Solution {
public:
    int getheight(TreeNode* node) {
        if (node == NULL) return 0;                  //遇到空节点终止，当前节点为根节点的树高度为0
        int leftheight = getheight(node->left);      //求左子树的高度
        if (leftheight == -1) return -1;             //迭代发现某一节点的左右子树不平衡
        int rightheight = getheight(node->right);    //求右子树的高度
        if (rightheight == -1) return -1;
        int result;                                          //如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。
        if (abs(leftheight - rightheight) > 1) result = -1;  //abs求数据的绝对值,判断左右子树是否平衡
        else result = 1 + max(leftheight, rightheight);      //以当前节点为根节点的树的高度
        return result;
    }

    bool isBalanced(TreeNode* root) {
        return getheight(root) == -1 ? false : true;
    }
};

化简后：

class SOlution {
public:
    int getheight(TreeNode* node) {
        if (node == NULL) return 0;           
        int leftheight = getheight(node->left);   
        int rightheight = getheight(node->right); 
        if (leftheight == -1 || rightheight == -1 || abs(leftheight - rightheight) > 1) return -1;
        else return max(leftheight, rightheight);
    }
    bool isBalanced(TreeNode* root) {
        return getheight(root) >= 0;
    }
};

待解
二叉树的所有路径
二叉树中递归带着回溯