公众号merlinsea
最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
思路1：递归
代码如下：
class Solution { public: int run(TreeNode *root) { if(root == nullptr) return 0; if(root->left == nullptr) // 若左子树为空，则返回右子树的最小深度+1 { return run(root->right)+1; } if(root->right == nullptr) // 若右子树为空，则返回左子树的最小深度+1 { return run(root->left)+1; } // 左右子树都不为空时，取较小值 int leftDepth = run(root->left); int rightDepth = run(root->right); return (leftDepth<rightDepth)?(leftDepth+1):(rightDepth+1); } };
思路二：层序遍历，非递归版本
从上到下，从左到右，当遇到第一个叶子节点的时候就可以判断当前高度为最低的高度。
注意点：
1、叶子节点的判断不是 node ==null ，是node！=null && node.left==null && node.right ==null
2、数据结构是队列queue
3、判断当前层结束采用哨兵机制
class Solution { public: typedef TreeNode* tree; int run(TreeNode *root) { if(!root) return 0; queue<tree> qu; tree last,now; int level; //last是当前层的最后一个节点，充当哨兵 last = now = root; level = 1; qu.push(root); while(qu.size()>0){ now = qu.front(); qu.pop(); if(now->left==nullptr && now->right==nullptr) break; if(now->left) qu.push(now->left); if(now->right) qu.push(now->right); if(last == now){ //当前层遍历结束，更新哨兵 level++; if(qu.size()) last = qu.back(); } } return level; } };
