# 树的遍历算法
# BFS (广度优先遍历) 模板代码
非递归方式，借用队列结构。
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
vector<vector<int>> levelOrderBottom1(TreeNode* root) {
vector<vector<int>> result;
queue<TreeNode*> mQueue;
int level = 0;
if (root == nullptr) {
return result;
}
mQueue.push(root);
while (!mQueue.empty())
{
result.push_back(vector<int>());
int size = mQueue.size();
for (int i = 0; i < size; i++) {
TreeNode* front = mQueue.front();
mQueue.pop();
result[level].push_back(front->val);
if (front->left != nullptr) {
mQueue.push(front->left);
}
if (front->right != nullptr) {
mQueue.push(front->right);
}
}
level++;
}
return result;
}
# DFS (深度优先遍历) 模板代码
非递归方式，借用栈数据结构
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
void dfs(TreeNode* root) {
vector<int> result;
stack<TreeNode*> mStack;
if(root != nullptr){
mStack.push(root);
}
while(!mStack.empty()){
TreeNode* node = mStack.top();
mStack.pop();
if(node->right != nullptr){
mStack.push(node->right);
}
if(node->left != nullptr){
mStack.push(node->left);
}
}
return result;
}
# 中序遍历非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19vector<int> midorder(TreeNode* root){
vector<int> res;
if(root == nullptr){
return res;
}
stack<TreeNode*> mStk;
if(!mStk.empty() || root != nullptr){
while(root!= nullptr){
mStk.push(root);
root = root->left;
}
TreeNode *node = mStk.top();
mStk.pop();
res.push(node->val);
root = node->right;
}
return res;
}
# 后序遍历非递归
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
26vector<int> postOrder(TreeNode* root){
vector<int> res;
if(root == nullptr){
return res;
}
stack<TreeNode*> mStk;
TreeNode* prev;
while(root!= nullptr || !mStk.empty()){
while(root != nullptr){
mStk.push(root);
root = root.left;
}
TreeNode* node = mStk.top();
if(node->right == null || node->right == prev){
mStk.pop();
res.push(node->val);
pre = node;
root = nullptr;
}else{
mStk.push(node->right);
root = node->right;
}
}
return res;
}
# 224 基本计算器
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
int calculate(string s) {
//定义栈存储参数
stack<int> nums;
//预存入一个数字0，防止首个字符是运算符号
nums.push(0);
//定义栈存储操作符
stack<char> ops;
bool f = false;
for(int i=0;i<s.length();i++){
if(s[i] ==' ')//遇到空格跳过
{
continue;
}else if(s[i] == '+' || s[i] == '-') //遇到运算符
{
f = false;
//判断运算符号签名的字符是否为左括号，如果是，则在参数栈增加一个参数，用于于防止左括号后首个字符是运算符的情况
if(i > 0 && s[i-1] == '('){
nums.push(0);
}
//推入符号
ops.push(s[i]);
}else if(s[i] == '(')//遇到左括号
{
f = false;
ops.push(s[i]);
}else if(s[i] == ')')//遇到右括号，先弹出符号栈栈顶的左括号（栈顶必须是左括号，否则表达式错误）
{
ops.pop();
if(!ops.empty() && ops.top() != '('){
//计算括号内与括号左边数字的计算结果
if(ops.top() == '+'){
int right = nums.top();nums.pop();
int left = nums.top();nums.pop();
nums.push(left + right);
ops.pop();
}else if(ops.top() == '-'){
int right = nums.top();nums.pop();
int left = nums.top();nums.pop();
nums.push(left - right);
ops.pop();
}
}
}
else//遇到数字
{
//遇到数字左边也是数字，那就将参数栈顶弹出，与当前数字组成更大的数，然后再压入
if(i>0 && s[i-1] >= '0' && s[i-1] <= '9' ){
int v = nums.top();nums.pop();
v = v*10 + (s[i] - '0');
nums.push(v);
}else{
//直接压入
nums.push(s[i] - '0');
}
//遇到数字右边也是数字，那么先不取符号栈中的符号进行运算，继续遍历
if(i+1<s.length() && s[i+1] >='0' && s[i+1] <= '9' ){
}else{
//参数参加计算得到新参数
if(!ops.empty()){
if(ops.top() == '+'){
int right = nums.top();nums.pop();
int left = nums.top();nums.pop();
nums.push(left + right);
ops.pop();
}else if(ops.top() == '-'){
int right = nums.top();nums.pop();
int left = nums.top();nums.pop();
nums.push(left - right);
ops.pop();
}
}
}
}
}
return nums.top();
}
# 二叉搜索树
性质一： 二叉搜索树的中序遍历是递增序列
# 由一个递增序列构建二叉搜索树
使用递归法构建 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
29
30TreeNode* buildBinarySearchTree(Vector<int>& nums){
return buildBinarySearchTree(nums,0,nums.size()-1);
}
TreeNode* buildBinarySearchTree(Vector<int>& nums, int left,int right){
if(left > right){
return nullptr;
}
int mid = (right - left) / 2 + left;
TreeNode* node = new TreeNode(nums[mid]);
node->left = buildBinarySearchTree(nums,left, mid-1);
node->right = buildBinarySearchTree(nums,mid+1,right);
return node;
}
