递归三部曲
使用递归遍历二叉树，按照如下三步顺序：
- 确定递归函数的参数和返回值
- 确定终止条件
- 确定单层递归的逻辑
参考代码
前序递归遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
preorder(root, ret);
return ret;
}
// 前序递归遍历
public void preorder(TreeNode head, List<Integer> list) {
if(head == null) {
return;
}
list.add(head.val);
preorder(head.left, list);
preorder(head.right, list);
}
}
中序递归遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
inorder(root, ans);
return ans;
}
// 中序递归遍历
public void inorder(TreeNode head, List<Integer> list) {
if(head == null) {
return;
}
inorder(head.left, list);
list.add(head.val);
inorder(head.right, list);
}
}
后序递归遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
postorder(root, ans);
return ans;
}
// 后序递归遍历
public void postorder(TreeNode head, List<Integer> list) {
if(head == null) {
return;
}
postorder(head.left, list);
postorder(head.right, list);
list.add(head.val);
}
}
