1 題目

求給定二叉樹(shù)的最小深度。最小深度是指樹(shù)的根結(jié)點(diǎn)到最近葉子結(jié)點(diǎn)的最短路徑上結(jié)點(diǎn)的數(shù)量。

2 解法

2.1 遞歸方法

要找到最小深度,首先要確定有根到葉的第一個(gè)葉節(jié)點(diǎn),也就是一層一層確定.所以有:

/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/class Solution { public:/*** * @param root TreeNode類(lèi) * @return int整型*/int run(TreeNode* root) {// write code hereif (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;if (root->left == NULL && root->right != NULL)return 1 + run(root->right);if (root->left != NULL && root->right == NULL)return 1 + run(root->left);return 1 + (run(root->left) < run(root->right) ?run(root->left) : run(root->right));}

性能太差:

2.2 非遞歸方法

用隊(duì)列的方式, 先把每一層的節(jié)點(diǎn)放進(jìn)隊(duì)列里面,然后在把子節(jié)點(diǎn)放進(jìn)隊(duì)列里面,并循環(huán)檢查頭節(jié)點(diǎn)是否為葉節(jié)點(diǎn).

代碼:

/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/class Solution { public:/*** * @param root TreeNode類(lèi) * @return int整型*/int run(TreeNode* root) {// write code hereif (root == nullptr)return 0;queue<TreeNode*> tmpQ;tmpQ.push(root);int depth = 1;while (!tmpQ.empty()) {int sum = tmpQ.size();for (int i = 0; i < sum; i ++) {TreeNode* tmp = tmpQ.front();tmpQ.pop();if (tmp->left == nullptr && tmp->right == nullptr)return depth;if (tmp->left != nullptr)tmpQ.push(tmp->left);if (tmp->right != nullptr)tmpQ.push(tmp->right);}depth ++;}} };

性能比遞歸好了不少:

總結(jié)

以上是生活随笔為你收集整理的leetcode 111 --- 二叉树最小深度的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。