Leetcode题解精讲之二叉树的基本理论(分类、四种遍历方式、存储方式)

0 专栏介绍

---

1 二叉树的基本概念

二叉树是计算机科学中一种重要的数据结构，二叉树可以为空，或者由根节点及其左右子树组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树可以用于实现各种算法和数据结构，例如二叉搜索树、堆、表达式树等。二叉树的特性使得它在计算机科学中具有广泛的应用，包括在数据库、编译器、图形图像处理等领域。

二叉树的链式定义为

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

2 二叉树的分类

常见的二叉树有：

• 满二叉树(Full Binary Tree)：每个节点要么没有子节点，要么有两个子节点，且所有叶节点位于同一层
  

• 完全二叉树(Complete Binary Tree)：除了最后一层外，每一层的节点都被填满，最后一层的节点尽可能靠左排列

• 平衡二叉树(Balanced Binary Tree)：任何节点的两棵子树的高度差不超过 1

• 排序二叉树(Binary Search Tree)：也称为二叉搜索树，左子树上所有节点的键值小于根节点的键值，右子树上所有节点的键值大于根节点的键值

• AVL树(AVL Tree)：平衡的二叉搜索树，确保任何节点的左右子树高度差不超过 1

3 二叉树的遍历

二叉树的遍历方式指的是中间节点的遍历顺序

递归遍历模板

void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;/* 定义遍历顺序vec.push_back(cur->val);    // 中traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右*/
}

迭代实现模板

vector<int> traversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if (root != NULL)st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop();/* 定义遍历顺序if (node->right)st.push(node->right); st.push(node);        st.push(NULL); if (node->left)st.push(node->left);*/} else {st.pop();     node = st.top();    st.pop();result.push_back(node->val); }}return result;
}

3.1 前序遍历

遍历顺序为根节点->左子树->右子树

3.1.1 递归实现

void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;vec.push_back(cur->val);    // 中traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右
}

3.1.2 迭代实现

vector<int> traversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if (root != NULL) st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop();if (node->right)				// 右st.push(node->right);  if (node->left)					// 左st.push(node->left);    st.push(node);                  // 中st.push(NULL);} else {st.pop();node = st.top();st.pop();result.push_back(node->val);}}return result;
}

3.2 中序遍历

3.2.1 递归实现

void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec);  // 左vec.push_back(cur->val);    // 中traversal(cur->right, vec); // 右
}

3.2.2 迭代实现

vector<int> traversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if (root != NULL)st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop();if (node->right)			// 右st.push(node->right); st.push(node);        	    // 中st.push(NULL); if (node->left)				// 左st.push(node->left);} else {st.pop();     node = st.top();    st.pop();result.push_back(node->val); }}return result;
}

3.3 后序遍历

3.3.1 递归实现

void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右vec.push_back(cur->val);    // 中
}

3.3.2 迭代实现

vector<int> traversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if (root != NULL) st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop();st.push(node);              // 中st.push(NULL);if (node->right)			// 右st.push(node->right);  if (node->left)				// 左st.push(node->left);    } else {st.pop();node = st.top();st.pop();result.push_back(node->val);}}return result;
}

3.4 层序遍历

3.4.1 递归实现

void order(TreeNode* cur, vector<vector<int>>& result, int depth)
{if (cur == nullptr) return;if (result.size() == depth) result.push_back(vector<int>());result[depth].push_back(cur->val);order(cur->left, result, depth + 1);order(cur->right, result, depth + 1);
}vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;int depth = 0;order(root, result, depth);return result;
}

3.4.2 迭代实现

vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;
}

4 二叉树存储模式

二叉树的链式存储如下所示

二叉树的顺序存储如下所示

5 其他技巧

• 二叉搜索树中序遍历得到的值序列是递增有序的

---

🔥 更多精彩专栏：

• 《ROS从入门到精通》
• 《机器人原理与技术》
• 《机器学习强基计划》
• 《计算机视觉教程》
• …