111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 111. 二叉树的最小深度 - 图1 返回它的最小深度 2

解题思路1-DFS

和【 二叉树的最大深度 】这题有所不同，这里需要注意的是当一个结点若其中一颗子树为空，则结点的最小深度并不是1，而是非空的那颗子树的最小深度

  1. class Solution {
  2. public:
  3.     int minDepth(TreeNode* root) {
  4.         if(root == NULL)
  5.             return 0;
  6.         //当前结点的其中一棵子树为空，最小深度是另一颗子树的最小深度
  7.         if(root->left == NULL  && root->right != NULL)
  8.              return minDepth(root->right) + 1;
  9.         if(root->right == NULL  && root->left != NULL)
  10.              return minDepth(root->left) + 1;
  11.         //要么两颗子树都为空，要么两颗子树都不为空
  12.         return min( minDepth(root->left), minDepth(root->right) ) +1;
  13.     }
  14. };

解题思路2-BFS

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == NULL) return 0;
        queue<TreeNode*> que;
        que.push(root);
        int minDep = 1;
        TreeNode* front;
        int sz;
        while(!que.empty()) {
            sz = que.size();
            //将当前队列中的所有结点(即同一环同一层的结点)向四周扩散
            for (int i = 0;i < sz;i++) {
                front = que.front();
                que.pop();
                //判断是否到达最近的叶子结点
                if(front->left == NULL && front->right == NULL)
                    return minDep;
                //将front的相邻结点加入到队列中
                if(front->left != NULL )
                    que.push(front->left);
                if(front->right != NULL)
                    que.push(front->right);
            }
            minDep++;  //增加步数
        }
        return minDep;
    }
};

BFS借助队列做到一步一步“齐头并进”，是可以在还没遍历完整颗树的时候就找到最短距离的。
DFS也能找到最短路径，但是实际上比BFS低效得多，因为DFS实际上是靠递归得堆栈记录走过的记录的，要找最短路径，则需要把二叉树中所有树杈都探索完，然后才能对比出最短路径有多长。