【数据结构初阶-oj】入门二叉树的入门oj

前言

本期带来二叉树入门oj题的分享，写二叉树的题，最重要的就是分治思想…

博主水平有限，不足错漏之处，望请斧正，感激不胜！

1. 单值二叉树

思路

每个结点值相等…

根 = 左子树 && 根 = 右子树，等量代换： a = b && b = c ==> a = c

所有只需要根 = 左子树 && 根 = 右子树，就满足单值二叉树

代码

bool isUnivalTree(struct TreeNode* root)
{
    if(root == NULL)
        return true;

    if(root->left != NULL && root->left->val != root->val)
        return false;
    if(root->right != NULL && root->right->val != root->val)
        return false;
    
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12

代码分析：

• 判断时，只判断能出结果的条件——不等则返回假，相等不用管，继续走
• 还需要考虑结构：左/右子树不为空就比，为空肯定就不比了

2. 相同的树

思路

结构相同，结点值相等…

分：

1. 判断值：根值等 && 左子树值等 && 右子树值等
2. 判断结构：左子树为空时，右子树也为空

治：递归判断 根、左子树、右子树的值和结构

代码

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    //前序遍历判断
    if(p == NULL && q == NULL)
        return true;
    
    if(p == NULL || q == NULL)
        return false;

    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
13
14
15

代码分析：

• 判断结构：
  • 两个都到空，满足结构相等
  • 只有一个到空，结构不等
• 判断值
• 满足pq的左子树相同 && pq的右子树相同

3.另一棵树的子树

思路

前序遍历，每次拿到的根传给 IsSameTree，判断相等

代码

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    //前序遍历判断
    if(p == NULL && q == NULL)
        return true;
    
    if(p == NULL || q == NULL)
        return false;

    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
22
23
24
25
26
27
28

代码分析：

• 这里的返回要求的不是两边都有子树了，而是找到一颗就够 —— 逻辑或

4. 翻转二叉树

思路

根的左右子树交换 ==> 左子树的左右子树交换，右子树的左右子树交换…

分：左右子树交换

治：递归交换左右子树

代码

struct TreeNode* invertTree(struct TreeNode* root)
{
    //递归交换左右子树
    if(root == NULL)
        return NULL;
    struct TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;

    invertTree(root->left);
    invertTree(root->right);

    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

代码分析：

• 即使左右子树交换了也不影响后续的交换：交换只在本根结点的子树内，和兄弟结点的子树互不影响

5.对称二叉树

思路

根结点没有对称可言，所以对称的判断从根结点的左右子树开始

如何判断对称？假设我们拿到图中 左2 和 右2：

1. 判断他俩的值和结构
2. 判断 左2 的左子树和 右2 的右子树 ，再判断 左2 的右子树和 右2 的左子树

分：判断根结点和子树

治：递归判断 左的左和 右的右 && 左的右 和 右的左

代码

bool Compare(struct TreeNode* left, struct TreeNode* right)
{
    if(left == NULL && right == NULL)
        return true;
    //比结构
    if(left == NULL || right == NULL)
        return false;
    //比值
    if(left->val != right->val)
        return false;

    //左的左 比 右的右
    //左的右 比 右的左
    return Compare(left->left, right->right)
        && Compare(left->right, right->left);
    
}

bool isSymmetric(struct TreeNode* root)
{
    return Compare(root, root);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

代码分析：

• 比值和结构和翻转二叉树类似
• 初始状态直接传root和root，而后递归 左的左和 右的右 && 左的右 和 右的左

6.平衡二叉树

思路

abs(左子树高度 - 右子树高度) >= 1，递归判断每棵子树

代码

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

    int lh = TreeHeight(root->left);
    int rh = TreeHeight(root->right);

    return lh > rh ? lh+1 : rh+1;
}

bool isBalanced(struct TreeNode* root)
{
    if(root == NULL)
        return true;
        
    //每个根的左右高度绝对值 <=1
    if(abs(TreeHeight(root->left) - TreeHeight(root->right)) > 1)
        return false;

    return isBalanced(root->left)
        && isBalanced(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

代码分析：

• 求树的高度再上一篇博客实现过
• 要求左右都满足平衡——逻辑与

7.二叉树的前序遍历

思路

前序遍历没什么问题，只不过这道题的接口要求我们把每个结点值放进数组

代码

int TreeSize(struct TreeNode* root)
{
    if(root == NULL)
        return 0;
    
    return TreeSize(root->left)
        + TreeSize(root->right)
        + 1;
}

void PreOrder(struct TreeNode* root, int* arr, int* pi)
{
    //遍历，并放到数组内
    if(root == NULL)
        return;

    //root ==> left ==> right
    arr[*pi] = root->val;
    (*pi)++;

    PreOrder(root->left, arr, pi);
    PreOrder(root->right, arr, pi);

}

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    int n = TreeSize(root);
    int* arr = (int*)malloc(sizeof(int) * n);
    *returnSize = n;
    int i = 0;

    PreOrder(root, arr, &i);

    return arr;
}
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

代码分析

• 和之前实现的前序遍历，区别仅在“输出”
• 中序后序同理

8.二叉树遍历

思路

输入的字符串为前序遍历字符串，根据它来建树就是：根 ==> 左 ==> 右，每次拿到新的一个字符放进根，再递归左子树右子树

最后中序遍历输出即可

代码

#include 
#include 
typedef char BTDataType;
typedef struct BTNode
{
    BTDataType val;
    struct BTNode* left;
    struct BTNode* right;
}BTNode;

BTNode* BuildTree(char* s, int* pi)
{
    if(s[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }

    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    root->val = s[(*pi)++];
    root->left = BuildTree(s, pi);
    root->right = BuildTree(s, pi);
    
    return root;
}

void InOrder(BTNode* root)
{
    if(root == NULL)
        return;
    
    InOrder(root->left);
    printf("%c ", root->val);
    InOrder(root->right);
}

int main() 
{
    char s[101];
    scanf("%s", s);
    int i = 0;
    BTNode* root = BuildTree(s, &i);
    InOrder(root);
}
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

代码分析

• 访问字符串需要留意，这里我们用 数组名+下标 的方式访问字符串
  • 下标在传参时传地址（每次用完一个字符往下走，需要改变下标的值）

---

今天的分享就到这啦，这里是培根的blog，期待与你共同进步！