• 关键字:二叉树、递归
  • 难度:简单
  • 前置知识:二叉树、递归
  • 题目大意:对于一棵二叉树,计算其所有叶子节点中深度最小的一个节点的深度

题目描述

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

解法

这道题目算是一道非常简单的题目,我们不妨设minDepth(t)表示“以t为根节点的子树中,所有叶子节点中深度最小的一个节点的深度”,那么我们想要求的答案就是minDepth(root)

那么如何求解minDepth(t)呢?

我们不妨分情况进行讨论:

  • 如果t是叶子节点,即不存在左儿子和右儿子,那么显然有minDepth(t) = 1
  • 如果t有左儿子,但是没有右儿子,那么显然有minDepth(t) = minDepth(t -> left) + 1
  • 如果t有右儿子,但是没有左儿子,那么显然有minDepth(t) = minDepth(t -> right) + 1
  • 如果t有两个儿子,那么就需要从这两种方案里面选一个使得minDepth(t)最小的,即minDepth(t) = min(minDepth(t -> left) + 1, minDepth(t -> right + 1)) = min(minDepth(root -> left), minDepth(root -> right)) + 1

这样一来,就将minDepth(t)这个问题转化成了两个规模较小的问题minDepth(t -> left)minDepth(t -> right),从而可以使用递归的方法进行求解,具体的实现请参考之后的代码。

参考代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        // 特殊情况处理
        if (root == NULL) return 0;
        // 分情况讨论
        if (root -> left == NULL && root -> right == NULL) return 1;
        if (root -> left != NULL && root -> right == NULL) return minDepth(root -> left) + 1;
        if (root -> left == NULL && root -> right != NULL) return minDepth(root -> right) + 1;
        return min(minDepth(root -> left), minDepth(root -> right)) + 1;
    }
};

登录发表评论 注册

反馈意见