用非递归算法求二叉树高度

可以使用层序遍历的方式，从根节点开始，每遍历一层就把高度加1，直到遍历完所有层即可获得二叉树的高度。以下是示例代码：

int getHeight(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    queue<Node*> q;
    q.push(root);
    int height = 0;
    while (!q.empty()) {
        int levelSize = q.size();
        for (int i = 0; i < levelSize; i++) {
            Node* node = q.front();
            q.pop();
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
        height++; // 遍历完一层后，高度+1
    }
    return height;
}

对于二叉树的每个结点，都要访问一次，时间复杂度为 O(N)，其中 N 是二叉树的结点数；空间复杂度为 O(W)，其中 W 是最大的层宽。