算法题： 树的深度

题目描述

Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

分析

最小深度问题，二叉树；递归求解，深度优先（左右子树先null先返回）采用广度优先，层次遍历，找到非满即为 minimum depth，引入队列辅助存储节点信息

代码

递归求解，深度优先j（javac） /** 1. Definition for binary tree 2. public class TreeNode { 3. int val; 4. TreeNode left; 5. TreeNode right; 6. TreeNode(int x) { val = x; } 7. } */ public class Solution { public int run(TreeNode root) { //为空则返回0，即表示空节点，同时检验输入合法性 if(root == null){ return 0; } //左右子树为空，叶子结点 if(root.left == null&&root.right ==null){ return 1; } //如果左右子树有一个为空 ，返回叶子节点 if(root.left==null || root.right==null){ return(Math.max(run(root.left), run(root.right)) + 1); } //返回深度较浅的 return Math.min(run(root.left), run(root.right)) + 1; } }

2. 广度优先（c++）

class Solution { public: int run(TreeNode *root) { //合法性检验 if(!root) return 0; queue<TreeNode*> Queue; TreeNode* last = root; TreeNode* now=NULL; unsigned int level=1,size=0; //入队 Queue.push(root); while(Queue.size()) { //队首元素赋值给now now = Queue.front(); //出队 Queue.pop(); size = Queue.size(); //若左子树不空则入队 if(now->left) Queue.push(now->left); //若右子树不空，入队 if(now->right) Queue.push(now->right); //Queue.size返回值类型为unsigned int //若队列长度未改变则是到了叶子节点 if(Queue.size()-size==0) break; //若该节点出入过队列则，不是叶子结点 if(last == now) { level++; if(Queue.size()) last = Queue.back(); } } return level; } };

总结

递归优点：代码简洁，递归缺点：递归涉及频繁自身调用，时间空间复杂度高，实际使用中应尽可能将递归转为非递归方法