热身题：二叉树的前序遍历
题目描述：
题目链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
递归解法：
关键点1
递归三部曲：
第一步：确定递归函数的返回值和参数列表
第二步：确定递归终止条件
第三步：确定单层递归逻辑
关键点2
前序遍历是：根左右
代码和注释：
/*** Definition for a binary tree node.* public 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 {//递归三部曲List<Integer> res = new LinkedList<>();public List<Integer> preorderTraversal(TreeNode root) {//执行递归函数traversal(root);return res;}//第一步：确定递归函数的返回值和参数列表public void traversal(TreeNode root){//第二步：确定递归终止条件if(root == null){return;}//第三步：确定单层递归逻辑//前序遍历//根res.add(root.val);//左traversal(root.left);//右traversal(root.right);}}
运行结果：
同理可解二叉树的后序遍历、中序遍历
145. 二叉树的后序遍历
题目链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
代码和注释：
/*** Definition for a binary tree node.* public 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 {List<Integer> res = new ArrayList<>();public List<Integer> postorderTraversal(TreeNode root) {//执行递归函数traversal(root);//返回结果return res;}//递归三部曲//第一步：确定递归函数的返回值和参数列表public void traversal(TreeNode root){//第二步：确定递归终止条件if(root == null){return;}//第三步：确定单层递归逻辑//后序遍历//左traversal(root.left);//右traversal(root.right);//根res.add(root.val);}
}
运行结果：
94. 二叉树的中序遍历
题目链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
代码和注释：
/*** Definition for a binary tree node.* public 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 {List<Integer> res = new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {//调用递归函数traversal(root);//返回值return res;}//递归三部曲//第一步：确定递归函数的返回值和参数列表public void traversal(TreeNode root){//第二步：确定递归函数的终止条件if(root == null){return;}//第三步：确定单层递归逻辑//中序遍历//左traversal(root.left);//根res.add(root.val);//右traversal(root.right);}
}
运行结果：
