欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode刷题——二叉树的最小深度

程序员文章站 2022-04-24 23:46:57
...

大家好,继续刷题,递归真的很难,虽然代码很短,但是感觉每次都要想很久,还是不熟练吧,看下今天的题。

LeetCode刷题——二叉树的最小深度

思路:个人理解,递归无非三要素,递归体,跳出条件,持续变化状态。先上代码

/**
 * 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)
            return 0;
        int l = minDepth(root -> left);
        int r = minDepth(root -> right);
        if(!l)
            return r + 1;
        if(!r)
            return l + 1;
        return min(l + 1, r + 1);
    }
};

如上,递归体为:

int l = minDepth(root -> left) + 1;
int r = minDepth(root -> right) + 1;

跳出条件为:

if(!root)
    return 0;

持续变化状态为:

if(!l)
    return r + 1;
if(!r)
    return l + 1;
return min(l + 1, r + 1);

我之前有点搞不清楚,是这么写的:

int l = minDepth(root -> left) + 1;
int r = minDepth(root -> right) + 1;

这么一看就很清楚了,我把状态更新和递归混为一体了,其实递归只是重复执行,它不负责更新状态,更新状态一般是在后面的return模块或者是迭代中函数的参数上体现,其他更新是没有用的。

希望后面能更顺利的写出递归!我们下期见!

相关标签: LeetCode