MENU

[编程题]minimum-depth-of-binary-tree

February 23, 2020 • Read: 164 • 技术技巧

题目来源

时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 32M,其他语言64M

题目描述

求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
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.

解题思路

  • 递归,若为空树返回0;
  • 若左子树为空,则返回右子树的最小深度+1;(加1是因为要加上根这一层,下同)
  • 若右子树为空,则返回左子树的最小深度+1;
  • 若左右子树均不为空,则取左、右子树最小深度的较小值,+1;

来自 @Msean

  • C++11,其中有一个是新的关键字nullptr, 如果我们的编译器是支持nullptr的话,那么我们应该直接使用nullptr来替代NULL的宏定义。正常使用过程中他们是完全等价的。

参考代码

// 运行时间:12ms
// 占用内存:1024k

class Solution {
public:
    int run(TreeNode *root) {
        if(root == nullptr) return 0;
        if(root->left == nullptr) return run(root->right)+1;
        if(root->right == nullptr) return run(root->left)+1;
        int leftDepth = run(root->left);
        int rightDepth = run(root->right);
        return (leftDepth<rightDepth)?(leftDepth+1):(rightDepth+1);
    }
};

参考文献

Archives QR Code Tip
QR Code for this page
Tipping QR Code