求二叉树高度的非递归算法
时间: 2023-05-10 20:55:47 浏览: 144
可以使用层次遍历的方式求解二叉树的高度,具体实现如下:
```
int getHeight(TreeNode* root) {
if (root == nullptr) {
return 0;
}
queue<TreeNode*> q;
q.push(root);
int height = 0;
while (!q.empty()) {
int size = q.size();
height++;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
}
return height;
}
```
这个算法的时间复杂度是 O(n),其中 n 是二叉树的节点数。
相关问题
求二叉树高度的递归和非递归算法
二叉树高度的递归算法可以通过递归遍历左右子树来求得,具体实现可以参考以下代码:
```java
public int height(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
```
二叉树高度的非递归算法可以使用层序遍历的方式来求得,具体实现可以参考以下代码:
```java
public int height(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int height = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
height++;
}
return height;
}
```
用非递归算法求二叉树高度
可以使用层序遍历的方式,从根节点开始,每遍历一层就把高度加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 是最大的层宽。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)