104. 二叉树的最大深度(递归法)

题解

思路：该题可以使用前序遍历或者后序遍历，使用前序求的是深度，后序遍历求的是高度。而根节点的高度就是深度。

代码(C++)：

//递归(1.确定递归函数的参数和返回值；2.确定终止条件；3.确定单层递归的逻辑)
//(后序遍历——高度)
class Solution2 {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        int leftLevel = maxDepth(root->left); //左
        int rightLevel = maxDepth(root->right); //右
        return 1 + max(leftLevel, rightLevel); //中
    }
};

//递归(1.确定递归函数的参数和返回值；2.确定终止条件；3.确定单层递归的逻辑)
//!!!!!!!!!!!!!!!!!!!!前序遍历——深度
class Solution3 {
public:
    int result;//用于记录最大深度
    void getDepth (TreeNode* node, int depth) {
        result = result > depth ? result : depth; // 中

        if (node->left == nullptr && node->right == nullptr) return;

        if (node->left != nullptr) { //左
            depth++; //深度+1
            getDepth(node->left, depth);
            depth--; //回溯，深度-1
        }
        if (node->right != nullptr) { //右
            depth++; //深度+1
            getDepth(node->right, depth);
            depth--; //回溯，深度-1
        }
        return;
    }

    int maxDepth(TreeNode* root) {
        result = 0;
        if (root == nullptr) return result;
        getDepth(root, 1);
        return result;
    }
};

参考链接：代码随想录