一：解题思路
方法一：递归法。
方法二：迭代法，利用二叉树的层级遍历的思想，找到与根节点最近的叶子节点，这个时候就知道二叉树的最小深度了。
二：完整代码示例 (C++版和Java版)
递归版C++:
//Time:O(n),Space:O(n)
class Solution { public: int min(int a, int b) { return a < b ? a : b; } int minDepth(TreeNode* root) { if (root == NULL) return 0; if ((root->left == NULL) && (root->right != NULL)) return minDepth(root->right) + 1; if ((root->left != NULL) && (root->right == NULL)) return minDepth(root->left) + 1; return min(minDepth(root->left),minDepth(root->right)) + 1; } };
迭代法C++:
//Time:O(n),Space:O(n) class Solution { public: int minDepth(TreeNode* root) { if (root == NULL) return 0; queue<TreeNode*> queue; queue.push(root); int depth = 1; while (!queue.empty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode* t = queue.front(); queue.pop(); if ((t->left == NULL) && (t->right == NULL)) return depth; if ((t->right != NULL)) queue.push(t->right); if ((t->left != NULL)) queue.push(t->left); } depth++; } return -1; } };
递归版Java:
class Solution { public int minDepth(TreeNode root) { if(root==null) return 0; if((root.left==null)&&(root.right!=null)) return minDepth(root.right)+1; if((root.left!=null)&&(root.right==null)) return minDepth(root.left)+1; return Math.min(minDepth(root.left),minDepth(root.right))+1; } }
迭代版Java:
class Solution { public int minDepth(TreeNode root) { if(root==null) return 0; Queue<TreeNode> queue=new LinkedList<>(); queue.add(root); int depth=1; while(!queue.isEmpty()) { int size=queue.size(); for(int i=0;i<size;i++) { TreeNode t=queue.poll(); if(t.left==null&&t.right==null) return depth; if(t.left!=null) queue.add(t.left); if(t.right!=null) queue.add(t.right); } depth++; } return -1; } }
原文：https://www.cnblogs.com/repinkply/p/12455723.html