今天主要学习了二叉树的基本概念，以及多种遍历方法。包含分别使用迭代思想和递归思想的前序遍历，中序遍历，后序遍历以及层次遍历。
二叉树的基础知识
二叉树
二叉树的种类可以分为满二叉树和完全二叉树。满二叉树指的是一个二叉树仅包含度为0和度为2的结点，并且度为0的节点在同一层。如图所示：
1
/ \
2 3
/ \ / \
4 5 6 7
完全二叉树是指除最底层节点可能没填满，其余每层节点数都达到最大值，并且最下层的结点集中在该层最左边的若干位置。下面是一个完全二叉树的辨析图
二叉搜索树
二叉搜索树是有序树。左子树所有节点的值均小于根节点的值，右子树所有节点的值均大于根节点的值。如下图所示
平衡二叉搜索树是一种特殊的二叉搜索树，又被称为AVL树。性质如下：他是一棵空树或左右子树的高度差绝对值不超过1.
在底层容器中，set，multimap，multiset的底层实现都是平衡二叉搜索树，所以增删操作为logn。
基本实现
一般存储二叉树时，会多使用到链表进行存储。而对于每个结点的属性，我们一般按照如下方式进行定义。需要定义节点的值以及指向左右子节点的指针。
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};遍历方式总结
二叉树的前序遍历
题目链接：144. 二叉树的前序遍历 - 力扣（LeetCode）
首先是递归的实现方法。为实现中左右的输出格式，需要先访问根节点，在分别访问左节点和右节点，代码实现如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void travel(TreeNode* node,vector<int> &vec)
{
if(node==NULL) return;
vec.push_back(node->val);
travel(node->left,vec);
travel(node->right,vec);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
travel(root,result);
return result;
}
};接着是迭代遍历方法，需要借助栈这一数据结构进行实现。依旧是先访问根节点，然后依次将右结点、左节点进行入栈操作。需要注意的是，这里是右结点先入栈，因为我们的输出顺序是中左右，左节点后入栈才能先出栈。这里的入栈顺序是需要推敲一下的。代码实现如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> ss;
if(root==NULL) return result;
ss.push(root);
while(!ss.empty())
{
TreeNode* node=ss.top();
ss.pop();
result.push_back(node->val);
if(node->right) ss.push(node->right);
if(node->left) ss.push(node->left);
}
return result;
}
};二叉树的中序遍历
题目链接：94. 二叉树的中序遍历 - 力扣（LeetCode）
首先是递归的实现方法。由于输出顺序是左中右，所以先递归处理左节点，接着访问根节点，最后递归处理右节点。代码实现如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void travel(TreeNode* root,vector<int> &vec)
{
if(root==NULL) return;
travel(root->left,vec);
vec.push_back(root->val);
travel(root->right,vec);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
travel(root,result);
return result;
}
};接着是迭代遍历方法。中序遍历的迭代遍历方法有些特殊，他的思想是先一直遍历左节点并入栈，直到左节点为空，此时将栈顶元素出栈并放入输出数组中，在遍历栈顶元素的右子树。其本质思想就是深度优先搜索，遇到空节点就进行回溯。还是有点难理解的，需要多写两遍。实现代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* cur=root;
while(cur!=NULL||!st.empty())
{
if(cur!=NULL)
{
st.push(cur);
cur=cur->left;
}
else
{
cur=st.top();
st.pop();
result.push_back(cur->val);
cur=cur->right;
}
}
return result;
}
};二叉树的后序遍历
题目链接：145. 二叉树的后序遍历 - 力扣（LeetCode）
对于递归遍历，思想与前面两种保持一致。由于顺序是左右中，所以依次递归处理左节点和右节点，最后访问根节点。实现思路如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void travel(TreeNode* root,vector<int> &vec)
{
if(root==NULL) return;
travel(root->left,vec);
travel(root->right,vec);
vec.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
travel(root,result);
return result;
}
};对于迭代遍历，后序遍历与前序遍历思想是一致的。后序输出顺序是左右中，那么我们只需要使用栈输出一个中右左，然后把输出数字进行翻转即可。由于是中右左，所以先入栈左节点在入栈右节点，输出时右结点就可以先行出栈，代码实现如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if(root!=nullptr) st.push(root);
while(!st.empty())
{
TreeNode* node=st.top();
st.pop();
result.push_back(node->val);
if(node->left) st.push(node->left);
if(node->right) st.push(node->right);
}
reverse(result.begin(),result.end());
return result;
}
};二叉树的层次遍历
题目链接：102. 二叉树的层序遍历 - 力扣（LeetCode）
首先还是先考虑递归处理，由于输出时需要保证相同层的数据在同一数组内。我们先考虑递归的终止条件，应该是所遍历的结点为空结点则返回。然后应该将该节点加入到这一深度下的数组，并递归处理左节点和右节点，深度要随之增加。代码实现如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void order(TreeNode* root,vector<vector<int>> &result,int depth)
{
if(root==NULL) return;
if(result.size()==depth) result.push_back(vector<int>());
result[depth].push_back(root->val);
order(root->left,result,depth+1);
order(root->right,result,depth+1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
order(root,result,0);
return result;
}
};接着是迭代遍历方法，需要借助队列这一数据结构。我们需要统计每一层的节点个数，按照个数进行出队列，并将左右节点进行入队列的操作。这样可以保证每一层的结点在不同的数组中，当一层的节点遍历完成，将该一维数组添加到二维数组中作为一层的输出结果。当队列为空说明遍历完成。代码实现如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void order(TreeNode* root,vector<vector<int>> &result,int depth)
{
if(root==NULL) return;
if(result.size()==depth) result.push_back(vector<int>());
result[depth].push_back(root->val);
order(root->left,result,depth+1);
order(root->right,result,depth+1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
order(root,result,0);
return result;
}
};总结
今天内容比较多。首先学习了二叉树的基本知识，包括满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树，以及二叉树的存储方式和遍历方式。对于前序、中序、后序、层次遍历、四种遍历方式，每一种都有递归处理和迭代处理两种写法。都需要熟练的联系和掌握。
标签：result,遍历,TreeNode,val,随想录,right,二叉树,root,left From： https://blog.csdn.net/m0_62154842/article/details/140610045