理论基础

递归3要素

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

迭代法思想：https://www.jianshu.com/p/bc1adf0a8418

递归就是指程序调用自身的编程思想，即一个函数调用本身；
迭代是利用已知的变量值，根据递推公式不断演进得到变量新值得编程思想。

常见应用迭代法：利用牛顿迭代法计算方程的解。

二叉树的遍历方式

• 深度优先遍历
  • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）
  • 后序遍历（递归法，迭代法）
  • 广度优先遍历
• 层次遍历（迭代法）

前序遍历：中左右DLR
中序遍历：左中右LDR
后序遍历：左右中LRD

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

**进阶：**递归算法很简单，你可以通过迭代算法完成吗？

方法一：递归

教程：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html#%E6%80%9D%E8%B7%AF

思路：

复杂度分析：

• 时间复杂度: $O(n)$

• 空间复杂度:最坏情况$O(n)$，在平衡情况下为O(logN)。

import java.util.ArrayList;
import java.util.List;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}
public class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();preorder(root,result);return result;}public void preorder(TreeNode root, List<Integer> result){//前序遍历：DLRif(root==null) return;result.add(root.val);preorder(root.left,result);preorder(root.right,result);}
}

方法二：迭代

教程：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html#%E6%80%9D%E8%B7%AF

思路：

复杂度分析：

• 时间复杂度: $O(n)$
• 空间复杂度:最坏情况$O(n)$，在平衡情况下为O(logN)。

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}
public class Solution {public List<Integer> preorderTraversal(TreeNode root) {//前序遍历：DLR,入栈顺序：D-R-L，D进再出，这样出栈是LRList<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){//stack不为空TreeNode node = stack.pop();result.add(node.val);//Dif (node.right != null){stack.push(node.right);//R}if (node.left != null){stack.push(node.left);}}return result;}
}

145. 二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点的数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

**进阶：**递归算法很简单，你可以通过迭代算法完成吗？

教程：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html#%E6%80%9D%E8%B7%AF

方法一：递归

思路：

复杂度分析：

• 时间复杂度: $O(n)$
• 空间复杂度:最坏情况$O(n)$，在平衡情况下为O(logN)。

import java.util.ArrayList;
import java.util.List;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();postorder(root,result);return result;}public void postorder(TreeNode root, List<Integer> result){//后序遍历：LRDif(root==null) return;postorder(root.left,result);postorder(root.right,result);result.add(root.val);}
}

方法二：迭代

教程：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html#%E6%80%9D%E8%B7%AF

思路：

复杂度分析：

• 时间复杂度: $O(n)$
• 空间复杂度:最坏情况$O(n)$，在平衡情况下为O(logN)。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}
public class Solution {public List<Integer> postorderTraversal(TreeNode root) {//后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){//stack不为空TreeNode node = stack.pop();result.add(node.val);//Dif (node.left != null){stack.push(node.left);//L}if (node.right != null){stack.push(node.right);//R}}Collections.reverse(result);return result;}
}

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

教程：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html#%E6%80%9D%E8%B7%AF

方法一：递归

思路：

复杂度分析：

• 时间复杂度: $O(n)$
• 空间复杂度:最坏情况$O(n)$，在平衡情况下为O(logN)。

import java.util.ArrayList;
import java.util.List;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();inorder(root,result);return result;}public void inorder(TreeNode root,List<Integer> result){//中序遍历：LDRif(root==null) return;inorder(root.left,result);result.add(root.val);inorder(root.right,result);}
}

方法二：迭代

教程：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html#%E6%80%9D%E8%B7%AF

思路：

复杂度分析：

• 时间复杂度: $O(n)$
• 空间复杂度:最坏情况$O(n)$，在平衡情况下为O(logN)。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}
public class Solution {public List<Integer> inorderTraversal(TreeNode root) {//中序遍历顺序: 左-中-右 入栈顺序： 左-右List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()){if (cur != null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();result.add(cur.val);cur = cur.right;}}return result;}
}