二叉树
整理了二叉树理论、算法、相关题目。参考代码随想录。
二叉树理论基础
二叉树的种类
满二叉树
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
满二叉树深度为k，则有2^k-1^个节点。
完全二叉树
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1)^ 个节点。
堆就是一棵完全二叉树，同时保证父子节点的顺序关系。
二叉搜索树
二叉搜索树是一个有序树。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树。
平衡二叉搜索树
又称为AVL树。它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn（unordered_map、unordered_set底层实现是哈希表）。
二叉树的存储方式
可以链式存储（用指针），可以顺序存储（用数组）。用数组存储二叉树遍历时，如果父节点的数组下标是i，则它的左孩子下标是2 * i + 1，右孩子是2 * i + 2。
二叉树的遍历方式
- 深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
- 广度优先遍历
- 层次遍历（迭代法）
二叉树的定义
C++ :
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
二叉树的递归遍历
递归三要素：确定递归函数的参数和返回值、确定终止条件、确定单层递归的逻辑。
- 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
- 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
- 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
144. 二叉树的前序遍历
题目
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
解法
class Solution {
public:
void traversal(TreeNode* node, vector<int>& vec)
{
if(node == nullptr)
return ;
vec.push_back(node->val);
traversal(node->left, vec);
traversal(node->right, vec);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vec;
traversal(root, vec);
return vec;
}
};
145. 二叉树的后序遍历
题目链接：145. 二叉树的后序遍历
94. 二叉树的中序遍历
题目链接：94. 二叉树的中序遍历
二叉树的迭代遍历
前序遍历（迭代法）
前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
为什么要先加入右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
144. 二叉树的前序遍历
题目
题目链接：144. 二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
解法
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> vec;
if(root == nullptr)
return vec;
st.push(root);
while(!st.empty())
{
TreeNode* node = st.top();
st.pop();
vec.push_back(node->val);
if(node->right != nullptr)
st.push(node->right);
if(node->left != nullptr)
st.push(node->left);
}
return vec;
}
};
后序遍历（迭代法）
前序是中左右，后序是左右中，所以将前序的入栈顺序先变成中右左，再把得到的序列反转就得到左右中。
题目
见上，略。
解法
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> vec;
if(root == NULL)
return vec;
st.push(root);
while(!st.empty())
{
TreeNode* node = st.top();
st.pop();
vec.push_back(node->val);
if(node->left != nullptr)
st.push(node->left);
if(node->right != nullptr)
st.push(node->right);
}
reverse(vec.begin(), vec.end());
return vec;
}
};
中序遍历（迭代法）
94. 二叉树的中序遍历
题目
题目链接：94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
解法
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> vec;
TreeNode* cur = root;
while(cur != nullptr || !st.empty())
{
if(cur != nullptr)
{
st.push(cur);
cur = cur->left;
}
else
{
cur = st.top();
st.pop();
vec.push_back(cur->val);
cur = cur->right;
}
}
return vec;
}
};
二叉树的层序遍历
102. 二叉树的层序遍历
题目
题目链接：102. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
解法
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
vector<vector<int>> result;
if(root)
que.push(root);
while(!que.empty())
{
vector<int> vec;
int size = que.size();
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;
}
};
107. 二叉树的层序遍历 II
题目
题目链接：107. 二叉树的层序遍历 II
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
解法
同上，最后把result reverse一下。
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result;
queue<TreeNode*> que;
if(root)
que.push(root);
while(!que.empty())
{
vector<int> vec;
int size = que.size();
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);
}
reverse(result.begin(), result.end());
return result;
}
};
199. 二叉树的右视图
题目
题目链接：199. 二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:
输入: [1,null,3]
输出: [1,3]
示例 3:
输入: []
输出: []
提示:
- 二叉树的节点个数的范围是
[0,100] -100 <= Node.val <= 100
解法
层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> result;
queue<TreeNode*> que;
if(root)
que.push(root);
while(!que.empty())
{
int size = que.size();
for(int i = 0; i < size; i++)
{
TreeNode* node = que.front();
que.pop();
if(i == size -1)
result.push_back(node->val);
if(node->left)
que.push(node->left);
if(node->right)
que.push(node->right);
}
}
return result;
}
};
637. 二叉树的层平均值
题目
题目链接：637. 二叉树的层平均值
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。
示例 2:
输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]
提示：
- 树中节点数量在
[1, 104]范围内 -231 <= Node.val <= 231 - 1
解法
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> result;
queue<TreeNode*> que;
if(root)
que.push(root);
while(!que.empty())
{
int size = que.size();
double sum = 0;
for(int i = 0; i < size; i++)
{
TreeNode* node = que.front();
que.pop();
sum += node->val;
if(node->left)
que.push(node->left);
if(node->right)
que.push(node->right);
}
result.push_back(sum / size);
}
return result;
}
};
429. N 叉树的层序遍历
题目
题目链接：429. N 叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
提示：
- 树的高度不会超过
1000 - 树的节点总数在
[0, 10^4]之间
解法
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> result;
queue<Node*> que;
if(root)
que.push(root);
while(!que.empty())
{
vector<int> vec;
int size = que.size();
for(int i = 0; i < size; i++)
{
Node* node = que.front();
que.pop();
vec.push_back(node->val);
for(int i = 0; i < node->children.size(); i++)
{
if(node->children[i])
que.push(node->children[i]);
}
}
result.push_back(vec);
}
return result;
}
};
515. 在每个树行中找最大值
题目
题目链接：515. 在每个树行中找最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
示例2：
输入: root = [1,2,3]
输出: [1,3]
提示：
- 二叉树的节点个数的范围是
[0,104] -231 <= Node.val <= 231 - 1
解法
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> result;
queue<TreeNode*> que;
if(root)
que.push(root);
while(!que.empty())
{
int size = que.size();
int max = INT_MIN;
for(int i = 0; i < size; i++)
{
TreeNode* node = que.front();
que.pop();
if(node->val > max)
max = node->val;
if(node->left)
que.push(node->left);
if(node->right)
que.push(node->right);
}
result.push_back(max);
}
return result;
}
};
116. 填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
111.二叉树的最小深度
总结
二叉树的层序遍历，就是图论中的广度优先搜索在二叉树中的应用，需要借助队列来实现。