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

在 C++ 中，非递归的中序遍历通常通过栈来实现，因为中序遍历需要先遍历左子树，然后访问根节点，最后遍历右子树。为了计算树的深度，你可以维护一个变量记录当前的最大深度。以下是一个简单的示例：

#include <iostream>
#include <stack>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0; // 空树的深度为0

    std::stack<TreeNode*> nodeStack;
    nodeStack.push(root);
    int depth = 1;

    while (!nodeStack.empty()) {
        int currentLevelSize = nodeStack.size();
        for (int i = 0; i < currentLevelSize; ++i) {
            TreeNode* currentNode = nodeStack.top();
            nodeStack.pop();

            // 如果有子节点，将它们压入栈里
            if (currentNode->left) {
                nodeStack.push(currentNode->left);
            }
            if (currentNode->right) {
                nodeStack.push(currentNode->right);
            }

            // 当前层遍历完毕，更新最大深度
            depth = std::max(depth, i + 1);
        }
    }
    return depth;
}

int main() {
    // 创建一个示例树
    TreeNode* tree = new TreeNode(1);
    tree->left = new TreeNode(2);
    tree->right = new TreeNode(3);
    tree->left->left = new TreeNode(4);

    int result = maxDepth(tree);
    std::cout << "Tree depth: " << result << std::endl;

    delete tree; // 别忘了删除动态分配的对象
    return 0;
}

在这个例子中，`maxDepth` 函数使用了迭代的方式，通过不断地将节点压入栈并更新当前层的大小，直到栈为空。每层遍历时，会检查是否有新的节点可以压入，如果有，则增加深度计数器；如果没有，说明已经到达最底层，更新最大深度。