如果中序遍历为有序的话则为二叉搜索树,为了避免退化为单链表,加入平衡规则后保持平衡则为平衡二叉树,搜索的时间复杂度为O(lgn).
满二叉树、完全二叉树又推出最大堆、最小堆(堆排序、定时器)。平衡二叉树又推出avl、红黑树。
对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
二叉树的递归遍历
前序遍历:根->左->右,1>2>4>5>3>6>7,245这棵树是作为一个整体子树从根节点遍历,这就是递归的思想。
中序遍历:左->根->右,4>2>5>1>6>3>7,每次遍历到子树也是重新左->根->右进行遍历。
后序遍历:左->右->根,4>5>2>6>7>3>1
1 | void PreOrder(TreeNode *root) |
二叉树的迭代遍历
栈是先进后出,前序遍历:根->左->右,1>2>4>5>3>6>7,所以要从右边往左进行压栈,顺序为右->左->根,思维方式恰好相反。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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59void PreOrder(TreeNode *root)
{
if (root == nullptr) return;
stack<TreeNode*> st;
st.push(root); // 先入根节点
while (!st.empty()) {
// 右->左->根
TreeNode* node = st.top(); st.pop();
if (node != nullptr) {
if (node->right != nullptr) st.push(node->right);
if (node->left != nullptr) st.push(node->left);
st.push(node);
st.push(nullptr); // 标记后面就是根节点
} else { // 遇到标记才打印根节点
node = st.top(); st.pop();
result.push_back(node->val);
}
}
}
void InOrder(TreeNode *root)
{
if (root == nullptr) return;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
// 右->根->左
TreeNode* node = st.top(); st.pop();
if (node != nullptr) {
if (node->right != nullptr) st.push(node->right);
st.push(node);
st.push(nullptr); // 标记后面就是根节点
if (node->left != nullptr) st.push(node->left);
} else { // 遇到标记才打印根节点
node = st.top(); st.pop();
result.push_back(node->val);
}
}
}
void PostOrder(TreeNode *root)
{
if (root == nullptr) return;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
// 根->右->左
TreeNode* node = st.top(); st.pop();
if (node != nullptr) {
st.push(node);
st.push(nullptr); // 标记后面就是根节点
if (node->right != nullptr) st.push(node->right);
if (node->left != nullptr) st.push(node->left);
} else { // 遇到标记才打印根节点
node = st.top(); st.pop();
result.push_back(node->val);
}
}
}
二叉树的层序遍历
广度优先搜索,需要使用队列来实现,和迭代类似,也是要让根节点先入,根节点弹出队列前,要把左右子节点入队列。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
29
30
31
32
33
34
35
36vector<int> traverse(TreeNode *root)
{
vector<int> result;
if (root == nullptr) return result;
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
size_t size = que.size();
for (size_t i = 0; i < size; i++) { // 这里可以不写,但要知道它的存在
TreeNode *node = que.front(); que.pop();
result.push_back(node->val);
if (node->left != nullptr) que.push(node->left); // 取出来后要将左右节点放进去
if (node->right != nullptr) que.push(node->right);
}
}
}
// 按层打印
vector<vector<int>> traverse(TreeNode *root)
{
vector<vector<int>> result;
if (root == nullptr) return result;
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
size_t size = que.size();
vector<int> res;
for (size_t i = 0; i < size; i++) { // 记录这一层有多少个节点
TreeNode *node = que.front(); que.pop();
res.push_back(node->val);
if (node->left != nullptr) que.push(node->left); // 取出来后要将左右节点放进去
if (node->right != nullptr) que.push(node->right);
}
result.push_back(res);
}
}
二叉树树形dp
求最优解问题、且子问题的解有重叠(某个节点的解是其父节点的一部分),需要找到状态转移方程。
从二叉树的节点A出发,可以向上或向下走,但沿途的节点只能经过一次,当达到节点B时,路径上的节点树叫做A到B到距离。
这棵树的最大距离(首先构建出这个模型,和高中的受力分析意义画出图来):max(左子树的最大距离,右子树的最大距离,左子树的高度+右子树的高度+1)
子问题的解有重叠:f(n-1)是f(n)解的一部分,确定边界值为某个叶子节点的解为f(0)=max(0, 0, 1)=1。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22struct RetVal { // 涉及到两个变量,先定义结构体
int distance;
int height;
RetVal(int dis, int hgt) : distance(dis), height(hgt) {}
};
int Do(TreeNode *root)
{
if (root == nullptr) return 0;
return dfs(root).distance;
}
// 后序遍历
RetVal dfs(TreeNode *root)
{
if (root == nullptr) return RetVal(0, 0);
RetVal left = dfs(root->left);
RetVal right = dfs(root->right);
int height = std::max(left.height, right.height) + 1; // 需要计算高度
// 左子树的最大距离,右子树的最大距离,左子树的高度+右子树的高度+1
return RetVal(std::max(std::max(left.distance, right.distance), left.height + right.height + 1), height);
}