三要素解决递归问题

编程基础 • 2024-12-31 12:30 • 阅读 13

本文运用递归来解决二叉树的一些基本问题，核心思想是紧抓三要素+ 一理解

三要素：

1）终止条件
2）本级递归要干什么
3）方法的返回值是什么

一理解：

解决递归问题，一定要从宏观上、广义上去看问题，千万不要纠结每一次递归在干什么，抓住起初的一级递归即可，否则会陷入无限套娃中

以下题为例

100. 相同的树 - 力扣（LeetCode）

上图第二步，在判断两颗二叉树是否相同的时候就需要用到宏观理解

上java代码

public boolean isSameTree(TreeNode p, TreeNode q) { if(p==null&&q==null){ // 两颗树都是空数，看做相同树 return true; } if(p==null||q==null){ // 一颗空树，另一颗非空树 return false; } if(p.val!=q.val){ // 结点值不等 return false; } if(!isSameTree(p.left,q.left)){ // 左节点代表的左子树不是相同树 return false; } if(!isSameTree(p.right,q.right)){ // 右节点代表的右子树不是相同树 return false; } // 两颗非空树满足上面三种情况，才是相同树 return true; }

利用逻辑与("&&")的短路特性简化代码

public boolean isSameTree(TreeNode p, TreeNode q) { if(p==null&&q==null){ return true; } if(p==null||q==null){ return false; } if(p.val!=q.val){ return false; } return p.val==q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right); }

个人理解：

笔者初学java和数据结构，理解不太透彻，如果描述不恰当，欢迎指正！！！

另外本文参考博客https://lyl0724.github.io/2020/01/25/1/

今天的文章三要素解决递归问题分享到此就结束了，感谢您的阅读。

三要素解决递归问题

相关推荐