資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++實現二叉樹的最小深度
在這個問題中，我們給定一棵二叉樹。我們的任務是找到二叉樹的最小深度。
二叉樹有一個特殊條件，即每個節點最多可以有兩個子節點。
二叉樹的最小深度是從根節點到任何葉子節點的最短路徑。
讓我們來看一個例子來理解這個問題：
輸入
輸出
2
解決方案
這個問題的解決方法是遍歷二叉樹並計算高度。這可以透過遞迴呼叫非葉子節點的子節點來完成，併為每個葉子節點返回1。
程式演示了我們解決方案的工作原理：
示例
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* left, *right;
};
int findMinDepthBT(Node *currentNode) {
if (currentNode == NULL)
return 0;
if (currentNode->left == NULL && currentNode->right == NULL)
return 1;
if (!currentNode->left)
return findMinDepthBT(currentNode->right) + 1;
if (!currentNode->right)
return findMinDepthBT(currentNode->left) + 1;
return min(findMinDepthBT(currentNode->left),
findMinDepthBT(currentNode->right)) + 1;
}
Node *newNode(int data) {
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
int main() {
Node *root = newNode(5);
root->left = newNode(2);
root->right = newNode(9);
root->left->left = newNode(5);
root->left->right = newNode(1);
root->left->left->left = newNode(7);
root->left->left->right = newNode(3);
cout<<"The minimum depth of binary tree is "<<findMinDepthBT(root);
return 0;
}輸出
The minimum depth of binary tree is 2
這種方法相當高效，但我們可以使用其他遍歷技術更有效地找到最小深度。
一種這樣的方法是使用層序遍歷，我們逐層遍歷樹。我們將返回我們遇到的第一個葉子節點的層數。
程式演示了我們解決方案的工作原理：
示例
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct lOrderQueue {
Node *node;
int depth;
};
int findMinDepthBT(Node *root) {
if (root == NULL)
return 0;
queue<lOrderQueue> levelOrder;
lOrderQueue deQueue = {root, 1};
levelOrder.push(deQueue);
while (levelOrder.empty() == false) {
deQueue = levelOrder.front();
levelOrder.pop();
Node *node = deQueue.node;
int depth = deQueue.depth;
if (node->left == NULL && node->right == NULL)
return depth;
if (node->left != NULL) {
deQueue.node = node->left;
deQueue.depth = depth + 1;
levelOrder.push(deQueue);
}
if (node->right != NULL) {
deQueue.node = node->right;
deQueue.depth = depth+1;
levelOrder.push(deQueue);
}
}
return 0;
}
Node* newNode(int data) {
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int main() {
Node *root = newNode(5);
root->left = newNode(2);
root->right = newNode(9);
root->left->left = newNode(5);
root->left->right = newNode(1);
root->left->left->left = newNode(7);
root->left->left->right = newNode(3);
cout<<"The minimum depth of binary tree is "<<findMinDepthBT(root);
return 0;
}輸出
The minimum depth of binary tree is 2
更新於：2021年3月12日
379 次瀏覽
廣告