题目描述

描述

求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。

示例

输入： {1,2,3,4,5}

返回值： 2

思路

最开始也想拿深度优先做来着，就是递归遍历到所有的叶子节点，然后记录最小值。但是考虑到递归太麻烦，而且不论树的结构如何，都要遍历所有的节点，就算配合一定的剪枝算法，也并不一定能够保证剪枝的效果。

因此考虑使用广度优先的算法，反正是寻找最小值，也就是说只要我从上到下在树的某一层寻找到了叶子节点，那么它必然是最小深度。

而且既然数据结构中给了一个val变量，就直接使用这个变量存储当前节点的深度就可以了。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int run(TreeNode* root) {
        if(root==NULL)										//处理空树情况
            return 0;
        queue<TreeNode> q;
        root->val = 1;
        q.push(*root);
        while(true)
        {
            TreeNode node = q.front();
            if(node.left == NULL && node.right == NULL)
            {
                return node.val;							//val的值即为节点深度。
            }
            else
            {
                if(node.left!=NULL)
                {
                    node.left->val = node.val+1;			//记录节点深度
                    q.push(*node.left);
                }
                if(node.right!=NULL)
                {
                    node.right->val = node.val+1;
                    q.push(*node.right);
                }
            }
            q.pop();
        }
    }
};