[数据结构]二叉树经典例题_数据结构二叉树遍历算法经典例题

---

单值二叉树

965. 单值二叉树

每一个结点检查它的左子树与右子树是否相等

bool isUnivalTree(struct TreeNode* root)
{
    if (root == NULL)
        return true;
    if (root->left && root->left->val != root->val) // 左子树存在且与根节点值相同
        return false;
    if (root->right && root->right->val != root->val)
        return false;
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}
1
2
3
4
5
6
7
8
9
10

---

二叉树的前序遍历

144. 二叉树的前序遍历

本题注意，_preorderTraversal（）中函数使用的是int* pi，因为在遍历左子树之后，将值填写入数组后，i的值应该++，如果传的不是指针，则还未进行++

int TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void _preorderTraversal(struct TreeNode* root, int* a, int* pi)
{
    if (root == NULL)
        return;
    a[(*pi)++] = root->val;
    _preorderTraversal(root->left, a, pi);
    _preorderTraversal(root->right, a, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int size = TreeSize(root);
    int* a = malloc(sizeof(int) * size); 
    int i = 0;
    _preorderTraversal(root, a, &i);
    *returnSize = size;
    return a;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

相同的树

100. 相同的树

时间复杂度O（N）：N个节点，每一个都要遍历

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    // 都为空
    if (p == NULL && q == NULL)
        return true;
    // 其中有一个是空
    if (p == NULL || q == NULL)
        return false;
    // 都不为空且p、q值相同
    if (p->val != q->val)
        return false;
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
1
2
3
4
5
6
7
8
9
10
11
12

---

对称二叉树

101. 对称二叉树

bool _isSymmetric(struct TreeNode* root1, struct TreeNode* root2)
{
    if (root1 == NULL && root2 == NULL)
        return true;
    if (root1 == NULL || root2 == NULL)
        return false;
    if (root1->val != root2->val)
        return false;
    return _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left);
}
bool isSymmetric(struct TreeNode* root){
    if(root == NULL)
        return true;
    return _isSymmetric(root->left, root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

另一棵树的子树

572. 另一棵树的子树

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    // 都为空
    if (p == NULL && q == NULL)
        return true;
    // 其中有一个是空
    if (p == NULL || q == NULL)
        return false;
    // 都不为空且p、q值相同
    if (p->val != q->val)
        return false;
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if (root == NULL)
        return false;
    if (isSameTree(root, subRoot))
        return true;
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

二叉树的遍历

二叉树遍历

描述
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述：
输入包括1行字符串，长度不超过100。
输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

示例1
输入：
abc##de#g##f###
输出：
c b e g d f a 
1
2
3
4
5
6
7
8
9
10
11
12

根据前序遍历还原树

#include <stdio.h>
#include <stdlib.h>

struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char val;
};
struct TreeNode* CreateTree(char* str, int* pi)
{
    if (str[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = str[(*pi)++];
    root->left = CreateTree(str, pi);
    root->right = CreateTree(str, pi);
    return root;
}

void InOrder(struct TreeNode* root)
{
    if (root == NULL)
        return;
    InOrder(root->left);
    printf("%c ", root->val);
    InOrder(root->right);
}
int main()
{
    char str[100];
    scanf("%s", str);
    int i = 0;
    struct TreeNode* root = CreateTree(str, &i);
    InOrder(root);
    return 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
40