算法与数据结构学习笔记:二叉树

本文最后更新于:November 28, 2021 am

知识点

二叉树遍历

前序遍历:先访问根节点,再前序遍历左子树,再前序遍历右子树 中序遍历:先中序遍历左子树,再访问根节点,再中序遍历右子树 后序遍历:先后序遍历左子树,再后序遍历右子树,再访问根节点

注意点

  • 以根访问顺序决定是什么遍历
  • 左子树都是优先右子树

前序遍历

例题:https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> ans;
vector<int> preorderTraversal(TreeNode* root) {

if(root==NULL)
return ans;
// 先访问根再访问左右
ans.push_back(root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
return ans;

}
};
非递归
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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if(root==NULL)
return ans;
stack<TreeNode*> st;
TreeNode *cur=root;
while(cur!=NULL||!st.empty())
{
while(cur!=NULL)
{
ans.push_back(cur->val);
st.push(cur);
cur=cur->left;
}
cur=st.top();
st.pop();
cur=cur->right;

}
return ans;

}
};

也可以这么写

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if(root==NULL)
return ans;
stack<TreeNode*> st;
st.push(root);
while(!st.empty())
{
auto cur=st.top();
st.pop();
ans.push_back(cur->val);
if(cur->right)
st.push(cur->right);
if(cur->left)
st.push(cur->left);
}

return ans;
}
};

中序遍历

例题:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int>ans;
vector<int> inorderTraversal(TreeNode* root) {
if(root==NULL)
return ans;
inorderTraversal(root->left);
ans.push_back(root->val);
inorderTraversal(root->right);
return ans;

}
};

后序遍历:

例题:https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

递归:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> ans;
vector<int> postorderTraversal(TreeNode* root) {
if(root==NULL)
return ans;
postorderTraversal(root->left);
postorderTraversal(root->right);
ans.push_back(root->val);
return ans;

}
};

分治法应用

先分别处理局部,再合并结果

适用场景

  • 快速排序
  • 归并排序
  • 二叉树相关问题

分治法模板

  • 递归返回条件
  • 分段处理
  • 合并结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ResultType traversal(TreeNode *root) {
// nil or leaf
if (!root) {
// do something and return
}

// Divide
auto left = traversal(root->left);
auto right = traversal(root->right);

// Conquer
auto result = merge(left, right);

return result;
}

典型示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// V2:通过分治法遍历二叉树
vector<int> preOrderTraversal(TreeNode *root) {
return divideAndConquer(root);
}

vector<int> divideAndConquer(TreeNode *root) {
vector<int> result;
if (!root) {
return result;
}
// 分治(Divide)
auto left = divideAndConquer(root->left);
auto right = divideAndConquer(root->right);
// 合并结果(Conquer)
result.push_back(root->val);
result.insert(result.end(), left.begin(), left.end());
result.insert(result.end(), right.begin(), right.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
27
28
29
30
31
32
33
34
35
36
37
38
39
template<typename T>
static void MergeSort(T arr[], int len) {
auto tmp = new T[len];
mergeSort(arr, 0, len - 1, tmp);
delete[] tmp;
}

template<typename T>
static void mergeSort(T arr[], int begin, int end, T tmp[]) {
if (begin + 1 >= end) {
return;
}

auto mid = begin + (end - begin) / 2;
auto begin1 = begin;
auto end1 = mid;
auto begin2 = mid + 1;
auto end2 = end;
mergeSort(arr, begin1, end1, tmp);
mergeSort(arr, begin2, end2, tmp);

// merge two parts
auto index = begin;
while (begin1 <= end1 && begin2 <= end2) {
tmp[index++] = arr[begin1] < arr[begin2] ? arr[begin1++] : arr[begin2++];
}

while (begin1 <= end1) {
tmp[index++] = arr[begin1++];
}

while (begin2 <= end2) {
tmp[index++] = arr[begin2++];
}

for (int i = begin; i <= end; ++i) {
arr[i] = tmp[i];
}
}

快速排序

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
template<typename T>
static void QuickSort(T arr[], int len) {
quickSort(arr, 0, len - 1);
}

template<typename T>
static void quickSort(T arr[], int begin, int end) {
if (begin >= end) {
return;
}
auto pivot = partition(arr, begin, end);
quickSort(arr, begin, pivot - 1);
quickSort(arr, pivot + 1, end);
}

template<typename T>
static int partition(T arr[], int begin, int end) {
auto base = arr[end];
auto lessInsert = begin;
for (int i = begin; i < end; ++i) {
if (arr[i] < base) {
swap(arr[lessInsert++], arr[i]);
}
}
swap(arr[lessInsert], arr[end]);
return lessInsert;
}

常见题目示例

104. 二叉树的最大深度
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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:

int maxDepth(TreeNode* root) {
if(root==NULL)
return 0;

int left=maxDepth(root->left);
int right=maxDepth(root->right);
if(left>right)
return left+1;
else
return right+1;


}
};
110. 平衡二叉树

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

3
/
9 20
/
15 7
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

1

/
2 2
/
3 3
/
4 4
返回 false 。

从底至顶

思路:分治法,左边平衡 && 右边平衡 && 左右两边高度 <= 1, 因为需要返回是否平衡及高度,要么返回两个数据,要么合并两个数据, 所以用-1 表示不平衡,>0 表示树高度(二义性:一个变量有两种含义)。

注意

一般工程中,结果通过两个变量来返回,不建议用一个变量表示两种含义

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(maxDepth(root)==-1)
{
return false;
}
return true;


}
int maxDepth(TreeNode *root)
{
if(root==NULL)
{
return 0;
}
int left=maxDepth(root->left);
int right=maxDepth(root->right);
if(left==-1||right==-1||left-right>1||right-left>1)
{
return -1;
}
if(left>right)
{
return left+1;
}
return right+1;
}
};
124. 二叉树中的最大路径和

给定一个非空二叉树,返回其最大路径和。

本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

示例 1:

输入: [1,2,3]

1

/
2 3

输出: 6
示例 2:

输入: [-10,9,20,null,null,15,7]

-10
/
9 20
/
15 7

输出: 42

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode* root) {
int res=INT_MIN;
helper(root,res);
return res;
}
int helper(TreeNode*root,int &val)
{
if(root==NULL)
return 0;
int left=max(0,helper(root->left,val));
int right=max(0,helper(root->right,val));
int lmr=root->val+left+right;
int ret=root->val+max(left,right);
val=max(val,max(lmr,ret));
return ret;



}
};
236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

img

示例 1:

1
2
3
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3

示例 2:

1
2
3
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

思路:分治法,有左子树的公共祖先或者有右子树的公共祖先,就返回子树的祖先,否则返回根节点

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL)
return root;
// 相等 直接返回root节点即可
if(root==p||root==q)
return root;
auto left=lowestCommonAncestor(root->left,p,q);
auto right=lowestCommonAncestor(root->right,p,q);
// 左右两边都不为空,则根节点为祖先
if(left!=NULL&&right!=NULL)
return root;
if(left!=NULL)
return left;
if(right!=NULL)
return right;
return NULL;

}
};

BFS 层次应用

102. 二叉树的层序遍历

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root==NULL)
return res;
queue<TreeNode *> q;
q.push(root);
while(!q.empty())
{
int currentLevelSize=q.size();
vector<int> level;
for(int i=0;i<currentLevelSize;i++)
{
auto cur=q.front();
level.push_back(cur->val);
q.pop();
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);
}
res.push_back(level);
}
return res;

}
};
107. 二叉树的层次遍历 II

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

思路:在层级遍历的基础上,翻转一下结果即可

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
if(root==NULL)
return res;
queue<TreeNode*>q;
q.push(root);
while(!q.empty())
{
int curLevelSize=q.size();
vector<int> curLevel;
for(int i=0;i<curLevelSize;i++)
{
auto cur=q.front();
q.pop();
curLevel.push_back(cur->val);
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);

}
res.push_back(curLevel);

}
reverse(res.begin(),res.end());
return res;
}
};
103. 二叉树的锯齿形层次遍历

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

例如:
给定二叉树 [3,9,20,null,null,15,7],

3
/
9 20
/
15 7
返回锯齿形层次遍历如下:

[
[3],
[20,9],
[15,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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root==NULL)
return res;
queue<TreeNode*> q;
q.push(root);
bool toggle=false;
while(!q.empty())
{
int curLevelSize=q.size();
vector<int> curLevel;
for(int i=0;i<curLevelSize;i++)
{
auto cur=q.front();
q.pop();
curLevel.push_back(cur->val);
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);

}
if(toggle)
{
reverse(curLevel.begin(),curLevel.end());
}
toggle=!toggle;
res.push_back(curLevel);
}
return res;
}
};

二叉搜索树应用

98. 验证二叉搜索树

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

中序遍历
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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
if(root==NULL)
return true;
vector<int>res;
inOrder(root,res);
for(int i=0;i<res.size()-1;i++)
{
if(res[i]>=res[i+1])
return false;
}
return true;


}
void inOrder(TreeNode*root,vector<int> &res)
{
if(root==NULL)
return;
inOrder(root->left,res);
res.push_back(root->val);
inOrder(root->right,res);
}
};
701. 二叉搜索树中的插入操作

给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

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
/**
* 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:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root==nullptr)
return new TreeNode(val);
if(root->val<val)
{
root->right=insertIntoBST(root->right,val);
}
else
{
root->left=insertIntoBST(root->left,val);
}
return root;

}
};