用c++实现：用后序递归算法求树的深度

在C++中，使用后序递归算法（也称为LRN递归，左-右-节点）计算二叉树的深度可以分为两个步骤：首先，你需要定义一个函数来表示访问节点的过程，然后在一个辅助函数中处理递归部分。

下面是一个简单的示例：

#include <iostream>
using namespace std;

// 定义二叉树节点结构体
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 后序遍历并计算深度
int maxDepth(TreeNode* root) {
    if (root == nullptr) { // 如果根节点为空，返回0
        return 0;
    }

    // 使用后序遍历策略，先递归处理左右子树，最后访问根节点
    int left_depth = maxDepth(root->left); // 左子树的深度
    int right_depth = maxDepth(root->right); // 右子树的深度

    // 返回两子树的最大深度加1（因为需要加上根节点）
    return max(left_depth, right_depth) + 1;
}

int main() {
    // 创建一个示例二叉树
    TreeNode* tree = new TreeNode(3);
    tree->left = new TreeNode(9);
    tree->right = new TreeNode(20);
    tree->right->left = new TreeNode(15);
    tree->right->right = new TreeNode(7);

    // 计算并打印深度
    int depth = maxDepth(tree);
    cout << "The maximum depth of the binary tree is: " << depth << endl;

    return 0;
}

在这个例子中，`maxDepth` 函数采用递归的方式，如果当前节点为空，则返回0，否则返回左右子树深度的最大值加1。在`main`函数中，我们创建了一个简单的二叉树实例，并计算其最大深度。