1. minimum-depth-of-binary-tree 二叉树的最小深度

Love The Way You Lie 2022-06-06 02:56 126阅读 0赞

## 题目描述 ##

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

给定一个二叉树，找到它的最小深度，最小深度是从根节点到最近叶节点的最短路径上的节点数。

## 题目解析 ##

这道题肯定是需要进行**按层遍历二叉树**，在遍历时，发现一个节点没有子节点，那么该节点所在的层数就是该二叉树的最小深度。

按层遍历二叉树这里不再赘述(Note: 往下看的话必须知道怎么遍历)，有个小难点就是如何把节点的层数记录下来。这里有很多种方法处理这个问题。

方法一：

新建一个队列与遍历树的队列保持一致，用于存储二叉树**层数**。每次推入和推出遍历队列时，同时推入推出层数队列。退出遍历的条件是遍历该节点时，其左右节点均是NULL，那么返回该节点的层数即可。

代码如下：

int run(TreeNode *root) 
        {
           if (NULL == root) return 0;
    
            queue<TreeNode *> nodeQueue;
            queue<int> indexQueue;
    
            nodeQueue.push(root);
            indexQueue.push(1);
    
            int id = 0;
            while (!nodeQueue.empty())
            {
                TreeNode *tmp = nodeQueue.front();
                id = indexQueue.front();
    
                nodeQueue.pop();
                indexQueue.pop();
    
                if (NULL == tmp->left && NULL == tmp->right)
                {
                    break;
                }
    
                if (NULL != tmp->left)
                {
                    nodeQueue.push(tmp->left);
                    indexQueue.push(id + 1);
                }
    
                if (NULL != tmp->right)
                {
                    nodeQueue.push(tmp->right);
                    indexQueue.push(id + 1);
                }
            }
            
            
            return id;
        }

方法二：(网上比较常见的方法)

记录当前遍历层的最后一个节点，当遍历的节点到了这个节点时，层数加1。退出条件与方法一相同。其实跟方法一相比换汤不换药，用了一个小技巧，不用去多一个队列去保存层数。

代码如下：

int run(TreeNode *root) 
        {
            if (NULL == root) return 0;
    
            queue<TreeNode *> nodeQueue;
            TreeNode * last = NULL;
    
            nodeQueue.push(root);
            last = root;
            
            int id = 1;
            
            while (!nodeQueue.empty())
            {
                TreeNode *tmp = nodeQueue.front();
                
                nodeQueue.pop();
    
                if (NULL == tmp->left && NULL == tmp->right)
                {
                    break;
                }
    
                if (NULL != tmp->left)
                {
                    nodeQueue.push(tmp->left);
                }
    
                if (NULL != tmp->right)
                {
                    nodeQueue.push(tmp->right);
                }
                
                if (last == tmp)
                {
                    id++;
                    last = nodeQueue.back();
                }
            }
            
            
            return id;
        }

方法三：

以上的两种方法均是用遍历的方法去做的，此题也可用递归的方式去做。

每个节点的最小层数是左子树和右子树相比较小的那个的层数加1得到。有一个特殊情况，就是左子树或者右子树为0，那么该节点的层数为另一个不为0的子树的层数+1得到。

递归的退出条件是：如果该节点为NULL，那么返回0。

代码如下：

int run(TreeNode *node) 
        {
            if (NULL == node) return 0;
            
            int l = run(node->left);
            int r = run(node->right);
            
            if (0 == l || 0 == r)
            {
                return 1 + l + r;
            }
            
            return 1 + min(l, r);
        }

这种方法代码段简单，但需要将整个二叉树全部遍历，且递归要有入栈出栈操作，目测效率比上两种方法低，不过需要实际测试对比才能知道准确结果。