代码随想录算法训练营day16(day18补) | 104.二叉树的最大深度 111.二叉树的最小深度 完全二叉树的节点个数

刷题笔记day16

104.二叉树的最大深度

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

想到的是用层序遍历的迭代法来做。

自己写的代码

层序遍历：

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

后序递归：

class Solution {
public:
    int getdepth(TreeNode* root) {
        if (!root) return 0;
        int leftdepth = getdepth(root->left);
        int rightdepth = getdepth(root->right);
        return 1 + max(leftdepth, rightdepth);
    }

    int maxDepth(TreeNode* root) {
        return getdepth(root);
    }
};

前序递归；

class Solution {
public:
    int result;
    void getdepth(TreeNode* root, int depth) {
        if (!root) return;
        if (!root->left && !root->right) result = max(result, depth);
        if (root->left) {
            getdepth(root->left, depth+1);
        }
        if (root->right) {
            getdepth(root->right, depth+1);
        }
        return;
    }
    int maxDepth(TreeNode* root) {
        result = 0;
        if (!root) return 0;
        getdepth(root, 1);
        return result;
    }
};

看了题解后的收获

层序遍历相当于一招鲜吃遍天了，但是效率会较低，递归法效率更高。

111.二叉树的最小深度

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

一侧是NULL一侧不是NULL的情况下忽略了后续的节点。

自己写的代码

后序递归：

class Solution {
public:
    int getdepth(TreeNode* root) {
        if (!root) return 0;
        if (root->left && !root->right) {
            return 1 + getdepth(root->left); 
        }
        if (!root->left && root->right) {
            return 1 + getdepth(root->right);
        }
        int leftdepth = getdepth(root->left);
        int rightdepth = getdepth(root->right);
        return 1 + min(leftdepth, rightdepth);
    }
    int minDepth(TreeNode* root) {
        return getdepth(root);
    }
};

前序递归：

class Solution {
private:
    int result;
    void getdepth(TreeNode* node, int depth) {
        // 函数递归终止条件
        if (!node) {
            return;
        }
        // 中，处理逻辑：判断是不是叶子结点
        if (node -> left == nullptr && node->right == nullptr) {
            result = min(result, depth);
        }
        if (node->left) { // 左
            getdepth(node->left, depth + 1);
        }
        if (node->right) { // 右
            getdepth(node->right, depth + 1);
        }
        return ;
    }

public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        result = INT_MAX;
        getdepth(root, 1);
        return result;
    }
};

看了题解后的收获

注意和最大深度的区别：
需要考虑左右节点中存在一个NULL节点的情况。

完全二叉树的节点个数

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

用的普通二叉树的遍历方法，时间复杂度为O(n);

自己写的代码

自己写的代码：

class Solution {
public:
    int nums;
    void countnums(TreeNode* node) {
        if (!node) return;
        ++nums;
        countnums(node->left);
        countnums(node->right);
    }
    int countNodes(TreeNode* root) {
        nums = 0;
        countnums(root);
        return nums;
    }
};

利用完全二叉树的性质：

class Solution {
public:
    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;
    }
};

看了题解后的收获

利用完全二叉树的性质，可达成时间复杂度：O(logn × logn)的算法。