leetcode_day16

今日内容：

• 104. 二叉树的最大深度

• 559. n叉树的最大深度

• 111. 二叉树的最小深度

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

树的最大深度

最大深度指从根到所有节点的长度中最长的那一个，换言之就是要找离根最远的节点然后返回到它的长度。

用DFS和BFS都行，分别代表递归前后序遍历和层序遍历，对于n叉树而言，仅仅是多比较几次而已，改写难度不大

下附对于n叉树的bfs遍历

int maxDepth(Node* root) {
    queue<Node *> q;
    if(root) q.push(root);
    int ans = 0;
    while(!q.empty()) {
        int size = q.size();
        for(int i = 0;i < size;i++) {
            Node * cur = q.front();
            q.pop();
            for(int j = 0;j < cur->children.size();j++) {
                q.push(cur->children[j]);
            }
        }
        ans++;
    }
    return ans;
}

二叉树的最小深度

最小深度需要注意，是从根到最近的叶子节点的距离，叶子节点指没有左右孩子的节点

所以在遍历时需要注意结束条件，对于层序遍历则判断当前节点是否是叶子，如果是就维护最小深度

对于递归遍历则根据子节点个数来分类处理，如果左右双全或双无，则直接递归；如果只有一个，就单独递归

下附递归遍历代码：

int minDepth(TreeNode* root) {
    if(!root) return 0;
    
    int left = minDepth(root->left);
    int right = minDepth(root->right);

    if(root->left == nullptr && root->right) {
        return 1 + right;
    }
    if(root->right == nullptr && root->left) {
        return 1 + left;
    }
    return 1 + min(left, right);
}

留坑，lc的最快执行代码中在最后return前把root的左右都指null，意义不明，但是就是快，没想出来为什么

完全二叉树的节点个数

用普通二叉树的遍历当然能做，只是不太好，还是用好完全二叉树的特性：非底层全满，底层从左往右堆

所以完全二叉树的左右子树深度肯定是一样的，如果不一样，那么再递归，直到递归到完全二叉树或者细粒度足够小时的空节点

代码贴的carl的，原文链接：代码随想录 | 完全二叉树的节点个数

int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    TreeNode* left = root->left;
    TreeNode* right = root->right;
    int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
    while (left) {  // 求左子树深度
        left = left->left;
        leftDepth++;
    }
    while (right) { // 求右子树深度
        right = right->right;
        rightDepth++;
    }
    if (leftDepth == rightDepth) {
        return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
    }
    return countNodes(root->left) + countNodes(root->right) + 1;
}