目录一、树型结构从生活到代码1.1 什么是树1.2 树的核心概念1.3 树的表示方法二、二叉树最常用的树结构2.1 什么是二叉树2.2 两种特殊的二叉树满二叉树完全二叉树2.3 二叉树的重要性质2.4 性质的应用几道经典练习题三、二叉树的存储与实现3.1 链式存储最常用3.2 手动构建一棵二叉树四、二叉树的遍历四种方式4.1 前序遍历Preorder4.2 中序遍历Inorder4.3 后序遍历Postorder4.4 层序遍历Level Order4.5 四种遍历的记忆口诀五、二叉树的核心操作实现5.1 获取节点个数5.2 获取叶子节点个数5.3 获取第K层节点个数5.4 获取二叉树的高度5.5 查找指定值的节点5.6 判断是否为完全二叉树六、常见面试题型精讲6.1 根据遍历序列还原二叉树6.2 检查两棵树是否相同6.3 翻转二叉树6.4 判断平衡二叉树七、总结与学习建议7.1 核心要点回顾7.2 学习路线建议7.3 推荐练习题目写在前面本文基于《二叉树》课程内容整理结合个人学习笔记和实践经验编写。所有示例代码均为独立编写旨在帮助读者系统地掌握二叉树这一核心数据结构。如需深入学习建议配合官方教材和LeetCode题目进行练习。一、树型结构从生活到代码1.1 什么是树在我们正式进入二叉树之前先聊聊更广义的树这个概念。树是一种非线性的数据结构由n个有限节点组成具有层次关系的集合。之所以叫树是因为它看起来像一棵倒挂的树——根在上叶在下。生活中的树形结构公司的组织架构CEO下面有各部门总监总监下面有经理经理下面有员工电脑的文件系统根目录下有文件夹文件夹里又有子文件夹和文件家族族谱祖辈繁衍出多个支系1.2 树的核心概念https://via.placeholder.com/400x250?textTreeStructure掌握以下术语就能看懂关于树的任何文章术语含义举例根节点没有父节点的节点公司CEO叶子节点度为0的节点基层员工父节点有子节点的节点部门主管子节点父节点的直接下级组员兄弟节点有相同父节点的节点同部门的同事节点的度一个节点拥有的子树个数CEO管3个总监度为3树的度所有节点中最大的度如果有总监管5个人树的度为5树的深度节点的最大层次数从CEO到实习生的层级数1.3 树的表示方法实际编码中最常用的是孩子兄弟表示法class TreeNode { int val; // 节点存储的数据 TreeNode firstChild; // 第一个孩子节点 TreeNode nextBrother; // 下一个兄弟节点 }这种表示法的好处是不管一个节点有多少个子节点我们都只需要两个指针——指向第一个孩子和下一个兄弟。这样就把任意树都转化成了二叉树的形式。二、二叉树最常用的树结构2.1 什么是二叉树二叉树是每个节点最多只有两个子树的树结构。这两个子树分别称为左子树和右子树且顺序不能颠倒。二叉树的核心特征每个节点最多有两个子节点度 ≤ 2子树有左右之分次序不能颠倒二叉树可以是空树2.2 两种特殊的二叉树满二叉树每一层的节点数都达到最大值。如果一个满二叉树的深度为K那么它的节点总数为2^K - 1。1 / \ 2 3 / \ / \ 4 5 6 7完全二叉树除了最后一层其他各层的节点数都达到最大值并且最后一层的节点都靠左排列。1 / \ 2 3 / \ / 4 5 6完全二叉树的一个重要性质可以用数组高效存储。因为它的节点编号和数组下标可以一一对应。2.3 二叉树的重要性质这些性质在面试和笔试中经常出现务必牢记性质1第i层最多有 2^(i-1) 个节点根节点在第1层性质2深度为K的二叉树最多有 2^K - 1 个节点性质3叶子节点数 度为2的节点数 1即 n₀ n₂ 1性质4具有n个节点的完全二叉树深度为 ⌊log₂n⌋ 1性质5对完全二叉树按层编号对于编号为i的节点父节点编号(i-1)/2i 0时左孩子编号2i 1如果存在右孩子编号2i 2如果存在2.4 性质的应用几道经典练习题题目1某二叉树共有399个节点其中有199个度为2的节点该二叉树的叶子节点数为根据性质3n₀ n₂ 1 199 1 200但等等——总节点数 n₀ n₁ n₂ 200 n₁ 199 399 n₁这等于399所以n₁ 0。这是可能的所以答案是200。题目2具有2n个节点的完全二叉树叶子节点个数为设叶子节点数为n₀度为2的节点数为n₂度为1的节点数为n₁。由性质3n₀ n₂ 1总节点数2n n₀ n₁ n₂ 2n₂ 1 n₁在完全二叉树中n₁只能是0或1。如果n₁0则2n 2n₂ 1左边偶数右边奇数不可能。所以n₁1。代入2n 2n₂ 2得n₂ n - 1所以n₀ n₂ 1 n。答案是n。三、二叉树的存储与实现3.1 链式存储最常用二叉树最常见的存储方式是链式存储每个节点包含数据和两个指针class TreeNode { int val; // 节点值 TreeNode left; // 左孩子引用 TreeNode right; // 右孩子引用 public TreeNode(int val) { this.val val; } }3.2 手动构建一棵二叉树为了后续学习遍历我们先手动创建一棵简单的二叉树public class BinaryTree { static class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val val; } } // 手动构建二叉树 public TreeNode createTree() { TreeNode A new TreeNode(1); TreeNode B new TreeNode(2); TreeNode C new TreeNode(3); TreeNode D new TreeNode(4); TreeNode E new TreeNode(5); TreeNode F new TreeNode(6); A.left B; A.right C; B.left D; B.right E; C.left F; return A; // 返回根节点 } }构建出的二叉树结构1 / \ 2 3 / \ / 4 5 6四、二叉树的遍历四种方式遍历是二叉树最基础也是最重要的操作。一共有四种遍历方式。4.1 前序遍历Preorder顺序根节点 → 左子树 → 右子树public void preOrder(TreeNode root) { if (root null) { return; } System.out.print(root.val ); // 访问根节点 preOrder(root.left); // 遍历左子树 preOrder(root.right); // 遍历右子树 }对于上面的树前序遍历结果1 2 4 5 3 64.2 中序遍历Inorder顺序左子树 → 根节点 → 右子树public void inOrder(TreeNode root) { if (root null) { return; } inOrder(root.left); // 遍历左子树 System.out.print(root.val ); // 访问根节点 inOrder(root.right); // 遍历右子树 }对于上面的树中序遍历结果4 2 5 1 6 34.3 后序遍历Postorder顺序左子树 → 右子树 → 根节点public void postOrder(TreeNode root) { if (root null) { return; } postOrder(root.left); // 遍历左子树 postOrder(root.right); // 遍历右子树 System.out.print(root.val ); // 访问根节点 }对于上面的树后序遍历结果4 5 2 6 3 14.4 层序遍历Level Order顺序从上到下从左到右逐层访问public void levelOrder(TreeNode root) { if (root null) { return; } QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { TreeNode cur queue.poll(); System.out.print(cur.val ); if (cur.left ! null) { queue.offer(cur.left); } if (cur.right ! null) { queue.offer(cur.right); } } }对于上面的树层序遍历结果1 2 3 4 5 64.5 四种遍历的记忆口诀遍历方式口诀根的位置前序根左右最前面中序左根右中间后序左右根最后面层序从上到下从左到右按层五、二叉树的核心操作实现掌握了遍历接下来我们实现二叉树的各种统计和查询功能。5.1 获取节点个数// 方式一遍历计数 public int size(TreeNode root) { if (root null) { return 0; } return size(root.left) size(root.right) 1; }5.2 获取叶子节点个数public int getLeafNodeCount(TreeNode root) { if (root null) { return 0; } if (root.left null root.right null) { return 1; // 叶子节点 } return getLeafNodeCount(root.left) getLeafNodeCount(root.right); }5.3 获取第K层节点个数public int getKLevelNodeCount(TreeNode root, int k) { if (root null || k 1) { return 0; } if (k 1) { return 1; // 第1层就是根节点本身 } return getKLevelNodeCount(root.left, k - 1) getKLevelNodeCount(root.right, k - 1); }5.4 获取二叉树的高度public int getHeight(TreeNode root) { if (root null) { return 0; } int leftHeight getHeight(root.left); int rightHeight getHeight(root.right); return Math.max(leftHeight, rightHeight) 1; }5.5 查找指定值的节点public TreeNode find(TreeNode root, int val) { if (root null) { return null; } if (root.val val) { return root; } // 先在左子树找 TreeNode leftResult find(root.left, val); if (leftResult ! null) { return leftResult; } // 左子树没找到再去右子树找 return find(root.right, val); }5.6 判断是否为完全二叉树public boolean isCompleteTree(TreeNode root) { if (root null) { return true; } QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { TreeNode cur queue.poll(); if (cur ! null) { queue.offer(cur.left); queue.offer(cur.right); } else { // 遇到null节点后队列中剩余的都应该是null while (!queue.isEmpty()) { if (queue.poll() ! null) { return false; } } } } return true; }思路利用层序遍历。遇到null节点后如果后面还有非null节点就不是完全二叉树。六、常见面试题型精讲6.1 根据遍历序列还原二叉树题型已知前序和中序遍历序列还原二叉树。例题前序EFHIGJK中序HFIEJKG求根节点。解法前序的第一个节点就是根节点。所以根节点是E。完整还原前序第一个E是根中序中E左边是H、F、I左子树右边是J、K、G右子树前序第二个F是左子树的根中序中F左边是H左子树右边是I右子树以此类推...6.2 检查两棵树是否相同public boolean isSameTree(TreeNode p, TreeNode q) { if (p null q null) { return true; } if (p null || q null) { return false; } if (p.val ! q.val) { return false; } return isSameTree(p.left, q.left) isSameTree(p.right, q.right); }6.3 翻转二叉树public TreeNode invertTree(TreeNode root) { if (root null) { return null; } // 交换左右子树 TreeNode temp root.left; root.left root.right; root.right temp; // 递归翻转左右子树 invertTree(root.left); invertTree(root.right); return root; }6.4 判断平衡二叉树public boolean isBalanced(TreeNode root) { return getHeight(root) ! -1; } private int getHeight(TreeNode root) { if (root null) { return 0; } int leftHeight getHeight(root.left); if (leftHeight -1) { return -1; // 左子树不平衡 } int rightHeight getHeight(root.right); if (rightHeight -1) { return -1; // 右子树不平衡 } if (Math.abs(leftHeight - rightHeight) 1) { return -1; // 高度差超过1不平衡 } return Math.max(leftHeight, rightHeight) 1; }七、总结与学习建议7.1 核心要点回顾二叉树是每个节点最多有两个子节点的树结构满二叉树和完全二叉树是两种特殊形态四种遍历前序根左右、中序左根右、后序左右根、层序递归是解决二叉树问题的核心思想掌握性质公式能快速解决选择题7.2 学习路线建议先理解概念画图理解树的层次结构和遍历过程手写代码自己实现遍历和各种统计方法刷题巩固在LeetCode上搜索二叉树标签从简单题开始进阶学习掌握二叉搜索树BST、平衡二叉树AVL、红黑树等7.3 推荐练习题目LeetCode 100相同的树LeetCode 101对称二叉树LeetCode 104二叉树的最大深度LeetCode 110平衡二叉树LeetCode 226翻转二叉树LeetCode 236二叉树的最近公共祖先如果你觉得这篇文章对你有帮助欢迎点赞收藏。下一篇我们将深入二叉搜索树看看如何利用二叉树的结构特性实现高效的查找和排序敬请期待注本文为个人学习总结所有代码示例均为独立编写。建议读者在学习过程中结合官方教材和LeetCode题目进行练习验证。
