二叉树算法详解和C++代码示例

二叉树（Binary Tree）是数据结构中的基础类型，广泛应用于查找、排序、图结构、表达式计算等算法中。下面将从 概念定义 → 分类 → 常用操作 → 核心算法 → C++代码示例 全面介绍。

---

一、二叉树基本概念

二叉树是一种每个节点最多有两个子节点（左孩子和右孩子）的树结构。常见术语：

• 根节点（root）：没有父节点的节点
• 叶子节点：没有任何子节点
• 高度：节点到叶子节点最长路径上的边数
• 完全二叉树：除了最后一层，其他层节点都满，且最后一层节点从左向右排列
• 满二叉树：所有非叶节点都有两个子节点

---

二、常见二叉树类型

类型	描述
普通二叉树	每个节点最多两个子节点
二叉搜索树（BST）	左子树值 < 当前节点 < 右子树值
平衡二叉树（AVL）	任意节点左右子树高度差 ≤ 1
完全二叉树	除最底层外都是满的，底层从左到右连续
堆（最大/最小堆）	满足堆性质的完全二叉树
红黑树 / Treap / 伸展树	自平衡 BST 的高级实现

---

三、常见操作和算法

操作	说明
插入 / 删除 / 查找	常用于 BST、AVL、红黑树
遍历	先序 / 中序 / 后序 / 层序遍历
最大最小值	通常用于 BST
高度 / 直径计算	深度优先搜索
判断平衡性、对称性、路径和	常见面试题考点

---

四、遍历方式详解与代码

1. 递归遍历（先序、中序、后序）

struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 先序
void preorder(TreeNode* root) {if (!root) return;std::cout << root->val << " ";preorder(root->left);preorder(root->right);
}// 中序
void inorder(TreeNode* root) {if (!root) return;inorder(root->left);std::cout << root->val << " ";inorder(root->right);
}// 后序
void postorder(TreeNode* root) {if (!root) return;postorder(root->left);postorder(root->right);std::cout << root->val << " ";
}

2. 层序遍历（BFS）

#include <queue>
void levelOrder(TreeNode* root) {if (!root) return;std::queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode* cur = q.front(); q.pop();std::cout << cur->val << " ";if (cur->left) q.push(cur->left);if (cur->right) q.push(cur->right);}
}

---

五、常见算法题示例（C++）

1. 判断是否为合法 BST

bool isValidBST(TreeNode* root, TreeNode* min = nullptr, TreeNode* max = nullptr) {if (!root) return true;if ((min && root->val <= min->val) || (max && root->val >= max->val)) return false;return isValidBST(root->left, min, root) && isValidBST(root->right, root, max);
}

2. 二叉树最大深度

int maxDepth(TreeNode* root) {if (!root) return 0;return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
}

3. 路径总和是否等于 target

bool hasPathSum(TreeNode* root, int sum) {if (!root) return false;if (!root->left && !root->right) return sum == root->val;return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}

---

六、二叉搜索树（BST）操作实现

插入节点

TreeNode* insert(TreeNode* root, int val) {if (!root) return new TreeNode(val);if (val < root->val) root->left = insert(root->left, val);else root->right = insert(root->right, val);return root;
}

查找最小值

int findMin(TreeNode* root) {while (root->left) root = root->left;return root->val;
}

---

七、刷题推荐（适合 LeetCode）

题目	类型
104. 二叉树最大深度	递归
226. 翻转二叉树	后序
110. 平衡二叉树	DFS + 剪枝
101. 对称二叉树	递归+比较子树结构
230. BST中第K小元素	中序遍历
124. 二叉树中的最大路径和	DFS回溯
236. 最近公共祖先（LCA）	递归思维
297. 二叉树序列化和反序列化	递归+层序

---

八、补充：建树方法

TreeNode* buildTree(const std::vector<int>& nodes, int& i) {if (i >= nodes.size() || nodes[i] == -1) { ++i; return nullptr; }TreeNode* root = new TreeNode(nodes[i++]);root->left = buildTree(nodes, i);root->right = buildTree(nodes, i);return root;
}
// 示例：{-1表示空指针}
// [1, 2, -1, -1, 3, -1, -1] 构建一颗根为1，左右为2,3的树

---

总结

方向	推荐算法题
遍历操作	先中后序，层序
递归思维	深度、路径和、翻转、判断 BST
搜索	最近公共祖先、寻找节点路径
构造树	根据前序+中序建树、序列化反序列化
优化技巧	剪枝、缓存、DFS+回溯

---