编写一个递归函数height，传入参数为二叉树根结点的指针root，计算二叉树的高度。 要求： （1）用自然语言简要描述算法思想； （2）用类C或C++语言形式的伪代码描述算法步骤； （3）分析算法的时间复杂度。

1. 算法思想：递归计算左子树和右子树的高度，将二者中的较大值加1，即为整棵二叉树的高度。

2. 伪代码：

int height(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return max(leftHeight, rightHeight) + 1;
}

3. 时间复杂度：假设二叉树中有n个结点，每个结点都只会被遍历一次，因此算法的时间复杂度为O(n)。

相关问题

编写一个递归函数height,传入参数为二叉树根节点的指针root计算二叉树高度

下面是C++代码实现：

int height(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int left_height = height(root->left);
    int right_height = height(root->right);
    return max(left_height, right_height) + 1;
}

递归函数的核心思想是求出左右子树的高度，然后取较大值加1即可。如果根节点为空，返回0。

编写一个递归函数，传入参数为一颗二叉树和一个值k，如果k出现在树中返回true，否则返回false。相应的写出非递归函数

递归函数：

bool findValue(TreeNode* root, int k) {
    if (root == NULL) {
        return false;
    }
    if (root->val == k) {
        return true;
    }
    return findValue(root->left, k) || findValue(root->right, k);
}

非递归函数：

bool findValue(TreeNode* root, int k) {
    if (root == NULL) {
        return false;
    }
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        if (node->val == k) {
            return true;
        }
        if (node->right != NULL) {
            s.push(node->right);
        }
        if (node->left != NULL) {
            s.push(node->left);
        }
    }
    return false;
}