本文为学习代码随想录时所做的笔记，仅供学习参考，不做任何商业用途，若有侵权，请联系删除。
二叉树理论基础篇
二叉树的种类
满二叉树
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
完全二叉树
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第
h 层，则该层包含 1~ 2^(h-1) 个节点。
二叉搜索树
二叉搜索树是一个有序树
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
平衡二叉搜索树
平衡二叉搜索树：又被称为AVL（Adelson-Velsky and
Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_map底层实现是哈希表。
二叉树的存储方式
链式存储
顺序存储
如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 +
1，右孩子就是 i * 2 + 2。
二叉树的遍历方式
- 深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
- 广度优先遍历
二叉树的定义
1
2
3
4
5
6
| struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
|
二叉树的递归遍历
每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！
确定递归函数的参数和返回值：
确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，
并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
1
| void traversal(TreeNode* cur, vector<int>& vec)
|
确定终止条件： 写完了递归算法,
运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
1
| if (cur == NULL) return;
|
确定单层递归的逻辑：
确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
1
2
3
| vec.push_back(cur->val);
traversal(cur->left, vec);
traversal(cur->right, vec);
|
前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
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> preorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
|
中序遍历
1
2
3
4
5
6
| void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) return;
traversal(cur->left, vec);
vec.push_back(cur->val);
traversal(cur->right, vec);
}
|
后序遍历
1
2
3
4
5
6
| void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) return;
traversal(cur->left, vec);
traversal(cur->right, vec);
vec.push_back(cur->val);
}
|
二叉树的迭代遍历
前序遍历（迭代法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if (root == NULL) return result;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
return result;
}
};
|
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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;
}
};
|
后序遍历（迭代法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if (root == NULL) return result;
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;
}
};
|
二叉树的统一迭代法
无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。
那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。
这种方法也可以叫做标记法。
迭代法中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
vector<int> inorderTraversal(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;
}
};
|
前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
vector<int> preorderTraversal(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;
}
};
|
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
vector<int> postorderTraversal(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;
}
};
|
二叉树的层序遍历
102.
二叉树的层序遍历 - 力扣（LeetCode）
需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
使用队列实现二叉树广度优先遍历，动画如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| # 递归法
class Solution {
public:
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;
}
};
|
翻转二叉树
226.
翻转二叉树 - 力扣（LeetCode）
递归法
1
2
3
4
5
6
7
8
9
10
| class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
|
迭代法
深度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
stack<TreeNode*> st;
st.push(root);
while(!st.empty()) {
TreeNode* node = st.top();
st.pop();
swap(node->left, node->right);
if(node->right) st.push(node->right);
if(node->left) st.push(node->left);
}
return root;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
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();
swap(node->left, node->right);
}
}
return root;
}
};
|
广度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
swap(node->left, node->right);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return root;
}
};
|
对称二叉树
101.
对称二叉树 - 力扣（LeetCode）
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。
递归法
确定递归函数的参数和返回值
1
| bool compare(TreeNode* left, TreeNode* right)
|
确定终止条件
1
2
3
4
| if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false;
|
确定单层递归的逻辑
1
2
3
4
| bool outside = compare(left->left, right->right);
bool inside = compare(left->right, right->left);
bool isSame = outside && inside;
return isSame;
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
bool compare(TreeNode* left, TreeNode* right) {
if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false;
bool outside = compare(left->left, right->right);
bool inside = compare(left->right, right->left);
bool isSame = outside && inside;
return isSame;
}
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
return compare(root->left, root->right);
}
};
|
迭代法
使用队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
queue<TreeNode*> que;
que.push(root->left);
que.push(root->right);
while (!que.empty()) {
TreeNode* leftNode = que.front(); que.pop();
TreeNode* rightNode = que.front(); que.pop();
if (!leftNode && !rightNode) {
continue;
}
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
return false;
}
que.push(leftNode->left);
que.push(rightNode->right);
que.push(leftNode->right);
que.push(rightNode->left);
}
return true;
}
};
|
使用栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
stack<TreeNode*> st;
st.push(root->left);
st.push(root->right);
while (!st.empty()) {
TreeNode* leftNode = st.top(); st.pop();
TreeNode* rightNode = st.top(); st.pop();
if (!leftNode && !rightNode) {
continue;
}
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
return false;
}
st.push(leftNode->left);
st.push(rightNode->right);
st.push(leftNode->right);
st.push(rightNode->left);
}
return true;
}
};
|
二叉树的最大深度
104.
二叉树的最大深度 - 力扣（LeetCode）
递归法
本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）
而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class solution {
public:
int getdepth(treenode* node) {
if (node == NULL) return 0;
int leftdepth = getdepth(node->left);
int rightdepth = getdepth(node->right);
int depth = 1 + max(leftdepth, rightdepth);
return depth;
}
int maxdepth(treenode* root) {
return getdepth(root);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class solution {
public:
int result;
void getdepth(treenode* node, int depth) {
result = depth > result ? depth : result;
if (node->left == NULL && node->right == NULL) return ;
if (node->left) {
depth++;
getdepth(node->left, depth);
depth--;
}
if (node->right) {
depth++;
getdepth(node->right, depth);
depth--;
}
return ;
}
int maxdepth(treenode* root) {
result = 0;
if (root == NULL) return result;
getdepth(root, 1);
return result;
}
};
|
迭代法
使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。
在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度，如图所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class solution {
public:
int maxdepth(treenode* root) {
if (root == NULL) return 0;
int depth = 0;
queue<treenode*> que;
que.push(root);
while(!que.empty()) {
int size = que.size();
depth++;
for (int i = 0; i < size; i++) {
treenode* node = que.front();
que.pop();
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return depth;
}
};
|
二叉树的最小深度
111.
二叉树的最小深度 - 力扣（LeetCode）
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
递归法
确定递归函数的参数和返回值
1
| int getDepth(TreeNode* node)
|
确定终止条件
1
| if (node == nullptr) return 0;
|
确定单层递归的逻辑
1
2
3
4
5
6
7
8
9
10
11
12
13
| int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
if (node->left == NULL && node->right != NULL) {
return 1 + rightDepth;
}
if (node->left != NULL && node->right == NULL) {
return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int getDepth(TreeNode* node) {
if (node == NULL) return 0;
int leftDepth = getDepth(node->left);
int rightDepth = getDepth(node->right);
if (node->left == NULL && node->right != NULL) {
return 1 + rightDepth;
}
if (node->left != NULL && node->right == NULL) {
return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;
}
int minDepth(TreeNode* root) {
return getDepth(root);
}
};
|
迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int minDepth(TreeNode* root) {
if (root == NULL) return 0;
int depth = 0;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
int size = que.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
if (!node->left && !node->right) {
return depth;
}
}
}
return depth;
}
};
|