谈谈递归与树
递归
递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法
递归代码示例:
void f(){
f();
}
上面这段代码为无限递归,在 Java 语言中,超过某个特定的阈值就会报栈溢出异常(因为JVM的方法栈容量是有限的)
所以我们在使用递归的时候,一般都会设置一个基线条件,来避免这种无限递归
void f(){
if (conditon){
return;
}
f();
}
树
这里以二叉树为例,它的定义是:
二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树
这里的一个重点是:一棵树的孩子又是一棵树
这就跟递归在概念上有了相似性了
两者的联系
如果将递归的概念映射到二叉树上面,我们就可以得到如下的结论:
- 递归的基线条件就是二叉树叶子节点的判定条件
- 对函数的递归调用就是对子树的访问(遍历)
应用
有了上面两个结论,许多关于树的算法就都可以使用递归来解决了,并且代码实现起来也会非常简单。
例子1:子树的前/中/后序遍历 https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
walk(root, list);
return list;
}
private void traversal(TreeNode root, List<Integer> list){
if (root == null) return;
traversal(root.left, list);
list.add(root.val);
traversal(root.right, list);
}
}
这里只需要调整 list.add 的顺序, 就可实现前序与后序遍历
例子2:翻转二叉树 https://leetcode-cn.com/problems/invert-binary-tree/
这道题重点在于左右子树引用的交换, 但本质还是树的遍历
class Solution {
public TreeNode invertTree(TreeNode root) {
invertTree0(root);
return root;
}
private void invertTree0(TreeNode root){
if (root == null) return;
TreeNode t = root.left;
root.left = root.right;
root.right = t;
if (root.left !=null) invertTree0(root.left);
if (root.right !=null) invertTree0(root.right);
}
}