【数据结构与算法 | 二叉树篇】二叉树的前中后序遍历(递归版本)

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);}
}