文章目录
- 概要
- 二叉树的基本概念
- 常见的二叉树类型
- 常用的二叉树遍历
- 二叉树的常用技巧
- 题目：二叉树的中序遍历
- 方法1--递归遍历
- 方法2--使用栈
概要
二叉树（Binary Tree）是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树在算法和计算机科学中具有广泛的应用，特别是在表达式解析、搜索算法、排序算法、优先级队列、堆和其他数据结构中。
二叉树的基本概念
- 节点 (Node)：二叉树中的每个元素。
- 根节点 (Root Node)：二叉树的顶端节点。
- 叶节点 (Leaf Node)：没有子节点的节点。
- 子节点 (Child Node)：某节点的直接后继。
- 父节点 (Parent Node)：某节点的直接前驱。
- 高度 (Height)：从根节点到叶节点的最长路径上的节点数。
- 深度 (Depth)：从根节点到某节点的路径上的节点数。
- 层次 (Level)：从根节点开始，第 1 层为根节点，其子节点为第 2 层，以此类推。
常见的二叉树类型
- 完全二叉树 (Complete Binary Tree)：除了最后一层，其他每一层的节点都达到最大数，最后一层的节点全部集中在最左边。
- 满二叉树 (Full Binary Tree)：每个节点要么是叶子节点，要么有两个子节点。
- 二叉搜索树 (Binary Search Tree, BST)：对于树中的每个节点，其左子树的所有节点值小于该节点值，右子树的所有节点值大于该节点值。
- 平衡二叉树 (Balanced Binary Tree)：左右子树的高度差不超过 1。
常用的二叉树遍历
- 前序遍历 (Pre-order Traversal)：根节点 -> 左子树 -> 右子树。
- 中序遍历 (In-order Traversal)：左子树 -> 根节点 -> 右子树。
- 后序遍历 (Post-order Traversal)：左子树 -> 右子树 -> 根节点。
- 层次遍历 (Level-order Traversal)：按层次从上到下、从左到右遍历。
二叉树的常用技巧
-
递归：
- 许多二叉树问题可以通过递归来解决，因为二叉树的结构天然适合递归思想。
- 例如，求二叉树的高度可以通过递归求左右子树的高度，然后取最大值加一。
-
迭代：
- 使用栈或队列来模拟递归过程，实现非递归的遍历方法。
- 例如，中序遍历可以通过显式栈来实现。
-
回溯：
- 回溯法常用于在树中寻找路径或解决路径问题。
- 例如，在路径和为某一值的情况下，回溯法可以在遍历的过程中动态构建路径并回退。
-
动态规划：
- 在处理一些优化问题时，可以在二叉树上应用动态规划，通过存储子问题的结果来减少重复计算。
- 例如，在二叉树上查找最长路径等问题中。
-
分治法：
- 将问题分解为若干子问题分别解决，然后合并子问题的结果。
- 例如，合并两棵二叉树、构造平衡二叉树等。
题目：二叉树的中序遍历
原题链接：二叉树的中序遍历
方法1–递归遍历
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();inorder(root, list);return list;}public void inorder(TreeNode root, List<Integer> list) {if (root == null) return;inorder(root.left, list);list.add(root.val);inorder(root.right, list);}
}方法2–使用栈
栈（Stack）：利用栈来模拟递归的行为。栈在遍历左子树时保存节点，确保能够回到父节点，并遍历右子树。
注意栈放入顺序和取出顺序相反。后进先出
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();LinkedList<TreeNode> stack = new LinkedList<>();while (root != null || !stack.isEmpty()) {while (root != null) {stack.push(root);root = root.left;}root = stack.pop();list.add(root.val);root = root.right;}return list;}
}
