几种遍历方式
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
|
void pre(Node *root){
if(root == NULL){
return;
}
cout << root -> val << endl;
pre(root->left);
pre(root->right);
}
void mid(Node *root){
if(root == NULL){
return;
}
mid(root->left);
cout << root -> val << endl;
mid(root->right);
}
void lst(Node *root){
if(root == NULL){
return;
}
lst(root->left);
lst(root->right);
cout << root -> val << endl;
}
|
计算二叉树深度
先计算左右子树的深度，然后整棵树的深度就是左右子树深度较大值加1（当前节点）
1
2
3
4
5
6
| int caculDepth(Node *root){
if(root == NULL){
return 0;
}
return max(caculDepth(root->left), caculDepth(root->right)) +1;
}
|
镜像二叉树
1
2
3
4
5
6
7
|
void Mirror(TreeNode *pRoot) {
if(pRoot == NULL) return;
Mirror(pRoot->left);
Mirror(pRoot->right);
swap(pRoot->left, pRoot->right);
}
|
从上往下打印出二叉树的每个节点，同层节点从左至右打印.
利用广度优先搜索思想。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
vector<int> PrintFromTopToBottom(TreeNode* root) {
queue<TreeNode*> q;
vector<int> v;
if(root == NULL) return v;
q.push(root);
while(!q.empty()){
TreeNode* node = q.front();
q.pop();
v.push_back(node->val);
if(node->left != NULL){
q.push(node->left);
}
if(node->right != NULL){
q.push(node->right);
}
}
return v;
}
|
