代码随想录算法训练营第16天-二叉树

注意点：貌似所有的二叉树题目，都可以通过层次遍历解决

104. 二叉树的最大深度

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

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

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

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

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

#递归
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftdepth = 0;
        int rightdepth = 0;
        leftdepth = 1 + maxDepth(root->left);
        rightdepth = 1 + maxDepth(root->right);
        return max(leftdepth, rightdepth);
    }
#层次遍历
    int maxDepth(TreeNode* root) {
        int depth = 0;
        if(root == nullptr) return depth;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            depth++;
            int size = q.size();
            while(size--) {
                TreeNode* node = q.front();
                q.pop();
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
        }
        return depth;
    }
};

559. N 叉树的最大深度

#层次遍历
   int maxDepth(Node* root) {
        int depth = 0;
        if (root == nullptr) return depth;
        queue<Node*> tq;
        tq.push(root);
        while(!tq.empty()) {
            depth++;
            int size = tq.size();
            while(size--) {
                Node* node = tq.front();
                tq.pop();
                int childrenSize = node->children.size();
                for (int i = 0; i<childrenSize;i++){
                    tq.push(node->children[i]);
                }
            }
        }
        return depth;
    }

111. 二叉树的最小深度

class Solution {
public:
    int minDepth(TreeNode* root) {
        int deepth = 0;
        if (root == nullptr) return deepth;
        queue<TreeNode*> tq;
        tq.push(root);
        bool isbreakloop = false;
        while (!tq.empty()) {
            deepth++;
            int size = tq.size();
            while(size--) {
                TreeNode* node = tq.front();
                tq.pop();
                if (node->left == nullptr && node->right == nullptr) {
                    isbreakloop = true;
                    break;
                }
                if (node->left) tq.push(node->left);
                if (node->right) tq.push(node->right);
            }
            if (isbreakloop == true) break;
        } 
        return deepth; 
    }
};

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

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

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