LeetCode刷题——二叉树的最小深度
程序员文章站
2022-04-24 23:46:57
...
大家好,继续刷题,递归真的很难,虽然代码很短,但是感觉每次都要想很久,还是不熟练吧,看下今天的题。
思路:个人理解,递归无非三要素,递归体,跳出条件,持续变化状态。先上代码
/**
* 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模块或者是迭代中函数的参数上体现,其他更新是没有用的。
希望后面能更顺利的写出递归!我们下期见!
上一篇: python映射列表实例分析
下一篇: 二叉搜索树的基本操作(递归和非递归)