力扣 [104、111、222]

104. 二叉树的最大深度

原题链接：

思路：

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans;
    void dfs (TreeNode* cur, int deepth) {
        if (cur == nullptr) {
            ans = max(deepth, ans);
            return ;
        }
        dfs (cur->left, deepth + 1);
        dfs (cur->right, deepth + 1);
        return;
    }

    int maxDepth(TreeNode* root) {
        dfs (root,0);

        return ans;
    }
};

111.二叉树的最小深度

原题链接：

思路：

1. 递归的出口：当前节点是叶子节点的时候，保留当前节点到根节点的深度。
2. 递归的返回值：无返回值。开全局变量比较每次叶子节点的深度。
3. 递归的每一级别操作：求当前树的深度。
4. 分情况讨论：是叶子节点和非叶子节点两种情况，如果是叶子节点的话，就保留记录当前的最小深度。如果不是叶子节点的话，就分别去递归当前左右子树的最小深度！

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans = 100010;
    void dfs (TreeNode* cur, int d) {
        //如果当前是叶子节点的话：
        if (cur->left == nullptr && cur->right == nullptr) {
            ans = min (d, ans);
            return ; 
        }

        //如果当前不是叶子节点的话：
        //那就去求分别求解左右子树的最小深度：
        if (cur->left) {
            dfs (cur->left, d + 1);
        }

        if (cur->right) {
            dfs (cur->right, d + 1);
        }

        return ;
    }

    int minDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        dfs (root, 1);
        return ans;
    }
};

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

原题链接：

思路：广度优先遍历

广度优先遍历即可，遍历一个，计数一次。

思路：深度优先遍历

1. 确定递归的参数和返回值：参数就是传入树的根节点，返回就返回以当前节点为根节点的子树的节点个数。所以返回值是 int 类型。
2. 确定终止条件：如果为空节点的话，就返回0，表示节点数=0。
3. 单层递归的逻辑：先求他的左子树的节点数量，再求右子树的节点数量，最后取总 + 1(子树的根节点！)，即为目前节点为根节点的子树节点的数量。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    int countNodes(TreeNode* root) {
        if (root == nullptr) {
            return 0 ;
        }
        queue<TreeNode*> q;
        q.push(root);
        int cnt=1;
        while (!q.empty()) {
            int n = q.size();   //记录当前层的节点个数！
            //遍历当前层的节点：
            for (int i=0; i < n; i ++) {
                //取出当前节点：
                TreeNode* t = q.front();
                q.pop();    //队头出队！
                //将当前层的左右子节点压入队列中：
                if (t->left) {
                    cnt ++;
                    q.push(t->left);
                }
                if (t->right) {
                    cnt ++;
                    q.push(t->right);
                }
            }
        }

        return cnt;
    }
};

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int dfs (TreeNode* cur) {
        //如果当前节点为空节点，说明节点数=0，返回0；
        if (cur == nullptr) {
            return 0;
        }

        //计算左右子树的节点数量：
        int l = dfs (cur->left);
        int r = dfs (cur->right);

        //思考一下：左右子树的节点是如何计算的：
        return l+r+1;
    }
    int countNodes(TreeNode* root) {
        return dfs(root);
    }
};