谈谈递归与树
递归
递归（英语：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);
}
}