代码随想录day16

104.二叉树的最大深度

题目：给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]，

? ? ? ? 做这道题之前需要先搞清楚高度与深度。

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）?

????????而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

? ? ? ? 还可用用先序来求二叉树的深度，但是会麻烦很多，主要是左右子树都递归会重复。

? ? ? ? 后序遍历：也可以认为是深度优先遍历

int maxDepth(struct TreeNode* root) {
    if(root==NULL) return 0;
    int left=maxDepth(root->left);
    int right=maxDepth(root->right);
    return fmax(left,right)+1;
}

? ? ? ? 迭代法：也可以理解为广度优先遍历，求最大深度也就是求层数。

class Solution {
public:
    //广度优先搜索
    int maxDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        queue<TreeNode*> myqueue;
        myqueue.push(root);
        int ans=0;
        while(!myqueue.empty()){
            int n=myqueue.size();
            //每次将一层的元素压入队，ans就加1
            while(n>0){
                TreeNode* node=myqueue.front();
                myqueue.pop();
                if(node->left) myqueue.push(node->left);
                if(node->right) myqueue.push(node->right);
                n--;
            }
            ans++;
        }
        return ans;
    }
};

?111.二叉树的最小深度

? ? ? ? 主要是返回条件，只有没有左右孩子的节点，才有可能是最小深度，而如果有左孩子，或者有右孩子，就说明不是最低点。

int minDepth(struct TreeNode* root) {
    if(root==NULL) return 0;
    int left=minDepth(root->right);
    int right=minDepth(root->left);
    if(root->left==NULL&&root->right!=NULL){
        return left+1;
    }
    if(root->left!=NULL&&root->right==NULL){
        return right+1;
    }
    int result=1+fmin(left,right);
    return result;
}

222.完全二叉树的节点个数

给出一个完全二叉树，求出该树的节点个数。

示例 1：

• 输入：root = [1,2,3,4,5,6]
• 输出：6

? ? ? ? 计算节点个数是左右子树的节点个数之和加上根节点。?

int countNodes(struct TreeNode* root) {
    if(root==NULL) return 0;
    int left=countNodes(root->left);
    int right=countNodes(root->right);
    return left+right+1;
}

? ? ? ? 迭代法：层序遍历,在模版上修改即可

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