首页 > 其他分享 >递归的进一步思考

递归的进一步思考

时间:2023-08-11 23:33:34浏览次数:34  
标签:node 左子 right return 递归 int 进一步 思考 left

翻转二叉树:

首先要想整体思路:

翻转一个二叉树就是先将左子树和右子树翻转,然后对作用左子树翻转函数(对左子树中的所有左右结点翻转),对右子树进行翻转函数

那么递归部分如下:

swap(node->left ,node->right);
reverse(node->left);
reverse(node->right);

这里需要注意的是reverse(node->left);和reverse(node->right);分别代表我遍历到了node->left,node->right这个结点,要对这两个结点进行操作

然后确定终止条件:也就是当二叉树是一个空树的时候什么都不做,直接返回node

然后带入图谱中看看需不需要加点什么(注意应是从右向左看,从而模拟弹栈的过程),遍历完图谱后可知不需要加什么程序,(注意如果没有返回值或则返回值仅仅起到一个表明什么都不做的作用,比如此题,那么就应该在遍历的时候将递归的代码删掉)因此整体程序就是:

    TreeNode* invertTree(TreeNode* node) {
        if (node == NULL) return node;
        swap(node->left, node->right);  // 中
        invertTree(node->left);         // 左
        invertTree(node->right);        // 右
        return node;
    }

左叶子之和

首先确定整体思路:
找到左子树的左叶子,找到右子树的左叶子,然后将它们的值加和

那么递归部分如下:

int left= sumfun(node->left);
int right= sumfun(node->right);
return right+left

 

然后确定终止条件,就是这个二叉树如果是一个空树的话,我们就返回0

然后带入图谱中看看需不需要加点什么(注意应是从右向左看,从而模拟弹栈的过程),感觉需要做点什么(注意如果有返回值那么就应该在遍历的时候将递归的代码换成下一层的返回值),应该在每层函数中遍历到左节点后,也就是运行到int left= sumfun(node->left);判断这个左节点是否为空,它的左右子节点是否为空,如果为空,那么就取这个左子节点就是左叶子结点那么就取这个左子节点的值,作为这一层的返回值。比如说3结点,运行到f(3)时,判断1结点的值是否为空,它的左右子节点是否为空,写成代码就是:

1 if (node->left && !node->left->left && !node->left->right) { // 左子树就是一个左叶子的情况
2     leftValue = node->left->data_;
3 }

然后根据上述代码知,node的子节点不能为空,否则node->left->left,node->left->right就会出异常,因此终止条件还得有:

 

1 if (node->left == NULL && node->right == NULL) return 0;

 

这个终止条件

因此整体代码为:

 

 1 int sumOfLeftLeaves(Node* node) {
 2     if (node == NULL) return 0;
 3     if (node->left == NULL && node->right == NULL) return 0;
 4 
 5     int leftValue = sumOfLeftLeaves(node->left);    // 左
 6     if (node->left && !node->left->left && !node->left->right) { // 左子树就是一个左叶子的情况
 7         leftValue = node->left->data_;
 8     }
 9     int rightValue = sumOfLeftLeaves(node->right);  // 右
10     int sum = leftValue + rightValue;               // 中
11 return sum;
12 }

 

标签:node,左子,right,return,递归,int,进一步,思考,left
From: https://www.cnblogs.com/Sandals-little/p/17624143.html

相关文章

  • 搭建B端产品帮助中心这两点很重要,从客户“帮助中心”出发思考!
    一款优质的产品若想要用户体验良好,除了需要客服解答外,一个全面完善的产品帮助中心也是必不可少的,尤其是对于B端产品来说,其重要性自然不言而喻。 产品帮助中心因为帮助中心是一个产品的重要用户自助服务模块,包括各类产品相关信息,用以帮助用户快速理解和使用产品功能,当我们产品开发......
  • 汉诺塔问题(递归)
    博客地址:https://www.cnblogs.com/zylyehuo/#_*_coding:utf-8_*_defhanoi(n,a,b,c):ifn>0:hanoi(n-1,a,c,b)print("movingfrom%sto%s"%(a,c))hanoi(n-1,b,a,c)hanoi(5,'A','B�......
  • 【专题】快消行业供应链转型思考与实践报告PDF合集分享(附原数据表)
    全文链接:https://tecdat.cn/?p=33411我们在这份报告合集中分享了有关中国本土企业的信息,包括快消品企业的渠道布局、所面临的外部风险和挑战,以及如何应对这些挑战。阅读原文,获取专题报告合集全文,解锁文末19份快消品行业相关报告。中国本土企业在制定价格策略方面,面临的......
  • 递归的用法
    递归主要有两难:1.判断递归方法的执行主体,具体从入参来看: 例如第一个递归方法入参是文件夹,确保了是可以保存文件。那么执行的时候就不需要判断入参是否是文件夹;第二个递归方法的入参是文件,不能确定是否是文件夹,需要第一步进行判断。但是两种方法都实现了查找文件夹下的文件的......
  • 递归算法练习C++
    1、逆波兰表达式(1)题目描述逆波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2+3的逆波兰表示法为+23。逆波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2+3)*4的逆波兰表示法为*+234。本题求解逆波兰表达式的值,其中运算符包括......
  • 代码随想录算法训练营第十四天| 理论基础 递归遍历 迭代遍历
     理论基础    卡哥建议:需要了解 二叉树的种类,存储方式,遍历方式 以及二叉树的定义   文章讲解:https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html   补充的知识点:   名词的概念看卡哥文章。二叉树......
  • 分解因数--递归算法
    【题目描述】给出一个正整数a,要求分解成若干个正整数的乘积,即a=a1×a2×a3×...×an,并且1<a1≤a2≤a3≤...≤an,问这样的分解的种数有多少。注意到a=a也是一种分解。【输入】第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a(1<a<32768)。【输出】n行,每......
  • 关于判定性问题和最优化问题的联系的一些思考
    关于判定性问题和最优化问题的联系的一些思考引入判定性问题判定性问题是指在某些约束条件下,给定命题判断是否成立的一系列问题。比如:给定一张无向图\(G\),判断图是否连通。答案只可能是两种:连通和不连通。这就是一个判定性问题。最优化问题最优化问题(optimizationpr......
  • 二叉树后序遍历非递归遍历实现图解
    二叉树的后序遍历输入:{1,#,2,3}返回值:[3,2,1]输入:{1}返回值:[1]代码实现publicint[]postorderTraversal(TreeNoderoot){TreeNodecur=root;List<Integer>list=newArrayList<>();Deque<TreeNode>stack=newArrayDeq......
  • loguru进一步封装解决打印日志定位异常问题
    importosimportsysimporttimefromloguruimportloggerimportinspectdefcreat_time_os():creat_time=time.strftime("%Y-%m-%d",time.localtime())sys.path.append(os.path.dirname(os.path.abspath(__file__)))log_path_dir=os.......