[数据结构与算法]【LeetCode-111 | 二叉树的最小深度】

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;


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 minDepth(TreeNode* root) {
        return getDepth(root);
    }  

    /* 递归法:后序遍历 */
    // 1.确定函数入参及返回值
    int getDepth(TreeNode* node) {
        // 2.确定递归终止条件
        if(node == nullptr) return 0;

        // 3.确定单层递归逻辑
        int leftDepth = getDepth(node->left);
        int rightDepth = getDepth(node->right);

        // 当根节点的左子树为空，但右子树不为空时，根节点不是最低点
        if(node->left == nullptr && node->right != nullptr) return 1 + rightDepth;

        // 当根节点的右子树为空，但左子树不为空时，根节点不是最低点
        if(node->left != nullptr && node->right == nullptr) return 1 + leftDepth;

        int result =  1 + min(leftDepth, rightDepth);
        return result;
    }
};