【数据结构与算法 | 二叉树篇】二叉树的前中后序遍历(递归版本)
1. 二叉树的概念
(1). 二叉树的结构
借用了一下力扣的模板
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;}}(2). 完全二叉树与满二叉树
概念这玩意还是几个月前看王卓老师的视频里学的，现在看的认识，但描述起来有点便秘啊有木有. 还可能讲错了.
(1). 满二叉树就是最后一层只有叶子节点，除最后一层以外全是度为2的节点.
(2). 完全二叉树就是只有度为2与度为0的节点.只有最后一层会出现叶子节点.
2. 力扣144 : 二叉树的前序遍历
(1). 题
给你二叉树的根节点 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
(2). 思路
口诀怼他个，前序遍历根左右.
(3). 解
class Solution {List<Integer> al = new ArrayList<>();public List<Integer> preorderTraversal(TreeNode root) {reverse(root);return al;}public void reverse(TreeNode root) {if (root == null) {return;}al.add(root.val);reverse(root.left);reverse(root.right);}
}3. 力扣94 : 二叉树的中序遍历
(1). 题
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
(2). 思路
口诀，左根右.
(3). 解
class Solution {List<Integer> al = new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {reverse(root);return al;}public void reverse(TreeNode root) {if (root == null) {return;}reverse(root.left);al.add(root.val);reverse(root.right);}
}4. 力扣145 : 二叉树的后序遍历
(1). 题
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[3,2,1]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
提示：
- 树中节点的数目在范围
[0, 100]内 -100 <= Node.val <= 100
(2). 思路
口诀，左右根搞定.
(3). 解
class Solution {List<Integer> al = new ArrayList<>();public List<Integer> postorderTraversal(TreeNode root) {reverse(root);return al;}public void reverse(TreeNode root) {if (root == null) {return;}reverse(root.left);reverse(root.right);al.add(root.val);}
}