做百度推广送的网站,网页制作的基本步骤和教程,网推推荐信,佛山企业管理咨询有限公司1 题目
求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
2 解法
2.1 递归方法
要找到最小深度,首先要确定有根到叶的第一个叶节点,也就是一层一层确定.所以有:
/*** struct TreeNode {* int val;* struct TreeNode *left;* struct…1 题目
求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
2 解法
2.1 递归方法
要找到最小深度,首先要确定有根到叶的第一个叶节点,也就是一层一层确定.所以有:
/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/class Solution {
public:/*** * param root TreeNode类 * 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 非递归方法
用队列的方式, 先把每一层的节点放进队列里面,然后在把子节点放进队列里面,并循环检查头节点是否为叶节点.
代码:
/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/class Solution {
public:/*** * param root TreeNode类 * return int整型*/int run(TreeNode* root) {// write code hereif (root nullptr)return 0;queueTreeNode* 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 ;}}
};
性能比递归好了不少:
