树的基础理论
树的定义
树是n（n>=0）个结点的集合。
n=0时为空树。
n!=0时，结点集合符合如下关系：
- 所有结点的集合中只有一个节点没有前驱结点，称为根结点。
- 除根结点外，其他结点有且只有一个前驱结点，对于没有后继结点的结点称为叶子结点。
- 结点集合中有多个终端结点。
树数据结构其实是图数据结构的一种。图的一些算法同样可用于树。
树的属性
结点关系
结点的度
该结点的后继节点的总数
分支结点
度>0的结点称为分支结点或非终端结点。（单分支结点、双分支结点）
叶子结点
度=0的结点称为叶子结点。
孩子结点
一个结点的后继结点为该结点的孩子结点。
双亲结点
一个结点是其后继结点的双亲结点。
子孙结点
一个结点的子树中除该结点外的所有结点成为该结点的子孙结点。
祖先结点
从树的根结点到某结点路径上通过的所有结点称为该结点的祖先结点。
兄弟结点
具有同一双亲的结点互相称为兄弟结点。
结点层次
树的一种层次结构。根结点为第一层，其孩子结点为第二层，依此类推。
树的度
所有结点的度的最大值称之为树的度
树的高度/树的深度
树种结点的最大层次。
树的性质
二叉树基础理论
二叉树的种类
满二叉树
如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
完全二叉树
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。
二叉搜索树
二叉搜索树是一个有序树。
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树
平衡二叉搜索树（AVL）
AVL（Adelson-Velsky and Landis）树
具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉树的存储方式
顺序存储
顺序存储的内存是连续的。使用数组记录。可以通过计算出下一元素的下标进行访问。
假设当前的节点下标为i，则其左子节点下标为i2+1，右子节点下标为i2+2。
链式存储
链式存储的内存是离散的。我们需要定义一个结构体,然后使用指针连接各个不同的存储地址。
1
2
3
4
5
6
7
8
| 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) {}
};
|
二叉树的遍历
二叉树的深度优先遍历
前序遍历
遍历顺序：中->左->右
力扣——二叉树的前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
| void traversal(TreeNode* node,vector<int>& record){
if(node == nullptr) return;
record.push_back(node->val);
traversal(node->left,record);
traversal(node->right,record);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
traversal(root,res);
return res;
}
|
使用栈模拟递归的行为。（因为递归的运行底层就是出栈入栈的过程）
注：
相关动画可以看这里：
力扣——代码随想录
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> record;
vector<int> res;
if(!root) return res;
record.push(root);
while(!record.empty()){
TreeNode* node = record.top();
record.pop();
res.push_back(node->val);
if(node->right) record.push(node->right);
if(node->left) record.push(node->left);
}
return res;
}
|
中序遍历
遍历顺序：左->中->右
力扣——二叉树的中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
| void traversal(TreeNode* node,vector<int>& record){
if(node == nullptr) return;
traversal(node->left,record);
record.push_back(node->val);
traversal(node->right,record);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
traversal(root,res);
return res;
}
|
- 循环迭代法
与前序遍历的迭代法不同。
首先使用一个指针迭代到树的左侧底部，记录经过的所有结点。
然后依次出栈，如果出栈结点的右结点不为空还需要遍历右子树的结点。
如此往复，直到栈空或指针为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> record;
vector<int> res;
TreeNode* cur = root;
while(cur || !record.empty()){
if(cur){
record.push(cur);
cur = cur->left;
}
else{
cur = record.top();
record.pop();
res.push_back(cur->val);
cur = cur->right;
}
}
return res;
}
|
后序遍历
遍历顺序：左->右->中
力扣——二叉树的后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
| void traversal(TreeNode* node,vector<int>& record){
if(node == nullptr) return;
traversal(node->left,record);
traversal(node->right,record);
record.push_back(node->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
traversal(root,res);
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> res;
if(root == nullptr) return res;
st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
st.pop();
res.push_back(node->val);
if(node->left) st.push(node->left);
if(node->right) st.push(node->right);
}
reverse(res.begin(),res.end());
return res;
}
|
二叉树的统一迭代遍历（深度优先搜索）
深度优先搜索使用栈（stack）记录临时节点。
要点：在中节点（两个子节点的双亲节点）入栈后再次插入一个nullptr（空节点）作为标记。
力扣——二叉树的统一迭代遍历
这里以中序遍历为例：
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
| vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
if(root != nullptr){
st.push(root);
}
while(!st.empty()){
TreeNode* node = st.top();
if(node){
st.pop();
if(node->right) st.push(node->right);
st.push(node);
st.push(nullptr);
if(node->left) st.push(node->left);
}
else{
st.pop();
node = st.top();
st.pop();
res.push_back(node->val);
}
}
return res;
}
|
二叉树的层序遍历（广度优先搜索）
广度优先搜索使用队列（queue）记录临时节点。
力扣——二叉树的层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
vector<vector<int>> res;
if(root) que.push(root);
while(!que.empty()){
int size = que.size();
vector<int> temp;
for(int i=0;i<size;i++){
TreeNode* node = que.front();
que.pop();
temp.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
res.push_back(temp);
}
return res;
}
|
二叉树的属性
二叉树的最大深度
力扣——二叉树的最大深度
力扣——N 叉树的最大深度
- 层序遍历
本人首先想到的是层序遍历求解
求二叉树的最大深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int maxDepth(TreeNode* root)
{
int depth=0;
queue<TreeNode*> qe;
if(root){
qe.push(root);
}
while(!qe.empty()){
int size = qe.size();
depth += 1;
for(int i=0;i<size;i++){
TreeNode* node = qe.front();
qe.pop();
if(node->left) qe.push(node->left);
if(node->right) qe.push(node->right);
}
}
return depth;
}
|
求n叉树的最大深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int maxDepth(Node* root) {
if(!root) return 0;
int depth =0;
queue<Node*> que;
que.push(root);
while(!que.empty()){
int size = que.size();
depth += 1;
for(int i=0;i<size;i++){
Node* node = que.front();
que.pop();
int nSize = node->children.size();
for(int j=0;j<nSize;j++){
if(node->children[j])
{
que.push(node->children[j]);
}
}
}
}
return depth;
}
|
1
2
3
4
5
| int maxDepth(TreeNode* root)
{
if(!root) return 0;
return 1+max(maxDepth(root->left),maxDepth(root->right));
}
|
二叉树的最小深度
力扣——二叉树的最小深度
与求最大深度不同的是，最小深度添加了一些用于判断是否到距离根节点最近的叶子节点的条件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int minDepth(TreeNode* root) {
if(!root) 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->right) que.push(node->right);
if(node->left) que.push(node->left);
if(!node->left && !node->right) return depth;
}
}
return depth;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int minDepth(TreeNode* root) {
if(!root) return 0;
if(root->left && !root->right){
int ld = minDepth(root->left);
return 1+ld;
}
else if(root->right && !root->left){
int rd = minDepth(root->right);
return 1+rd;
}
int ld = minDepth(root->left);
int rd = minDepth(root->right);
return 1+min(ld,rd);
}
|
对称二叉树
力扣——对称二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| bool compare(TreeNode* left,TreeNode* right){
if(!left && right){
return false;
}
else if(left && !right){
return false;
}
else if(!left && !right){
return true;
}
else if(left->val != right->val){
return false;
}
else{
bool l = compare(left->left,right->right);
bool r = compare(left->right,right->left);
return r&&l;
}
}
bool isSymmetric(TreeNode* root) {
if(!root) return true;
return compare(root->left,root->right);
}
|
完全二叉树的节点个数
力扣——完全二叉树的节点个数
1
2
3
4
5
6
| int countNodes(TreeNode* root) {
if(!root) return 0;
int l = countNodes(root->left);
int r = countNodes(root->right);
return l+r+1;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int countNodes(TreeNode* root) {
if(!root) return 0;
queue<TreeNode*> que;
que.push(root);
int res = 0;
while(!que.empty()){
int size = que.size();
for(int i=0;i<size;i++){
TreeNode* node = que.front();
que.pop();
res ++;
if(node->right) que.push(node->right);
if(node->left) que.push(node->left);
}
}
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int countNodes(TreeNode* root) {
if(!root) return 0;
TreeNode* left = root->left;
TreeNode* right = root->right;
int leftDepth = 0;
int rightDepth = 0;
while(left){
left = left->left;
leftDepth ++;
}
while(right){
right = right->right;
rightDepth ++;
}
if(rightDepth == leftDepth){
return (2<<leftDepth)-1;
}
return 1+countNodes(root->left)+countNodes(root->right);
}
|
二叉树的修改与构造
翻转二叉树
力扣——翻转二叉树
1
2
3
4
5
6
7
| TreeNode* invertTree(TreeNode* root) {
if(!root) return root;
swap(root->right,root->left);
invertTree(root->left);
invertTree(root->right);
return root;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| TreeNode* invertTree(TreeNode* root) {
stack<TreeNode*> st;
if(root) 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;
}
|
二叉树的公祖先问题
二叉搜索树的属性
二叉搜索树的修改与构造
