二叉树知识回顾——【树】之二叉树(C语言)(含图解)_半生瓜のblog-CSDN博客

二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)

本题中，对于C++或者Java等语言，返回的是它们的数据结构库里面的数据结构，而C语言没有，这也就是如果用C语言往后通吃数据结构会困难的原因。

注意本体的传参，操作的是不是一个数。

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;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 //计算结点个数
 int TreeSize(struct TreeNode* root)
 {
     return root == NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
 }
 //前序遍历
void _preorder(struct TreeNode* root,int* a,int *i)//为了保证一直对一个i进行操作所以要传地址
{
    if(root == NULL)
    {
        return ;
    }
    a[*i] = root->val;
    (*i)++;
    _preorder(root->left,a,i);
    _preorder(root->right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
     int size = TreeSize(root);
     //创建数组
     int* a = (int*)malloc(size*sizeof(int));
     int i = 0;
     _preorder(root,a,&i);
     *returnSize = size;
     return a;
}

二叉树的最大深度

经典的分治问题

104. 二叉树的最大深度 - 力扣（LeetCode） (leetcode-cn.com)

一棵树的高度就是最长路径的结点个数。

  • 空 - 高度为0
  • 非空 左右子树深度大的内个+1

本质上用的后序遍历，先求左，后求右边，再求自己。

图示

image-20210618084730107

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int maxDepth(struct TreeNode* root){
    if(root == NULL)
        return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);

    return leftDepth > rightDepth?leftDepth+1:rightDepth+1;
}

平衡二叉树

Loading Question… - 力扣（LeetCode） (leetcode-cn.com)

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;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxDepth(struct TreeNode* root){
    if(root == NULL)
        return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);

    return leftDepth > rightDepth?leftDepth+1:rightDepth+1;
}

bool isBalanced(struct TreeNode* root){
    //空树也满足条件
    if(root == NULL)
    {
        return true;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    //如果一开始就不满足就没必要往下进行了，满足就递归判断左右
    return abs(leftDepth-rightDepth) < 2
    && isBalanced(root->left)
    && isBalanced(root->right);                                          
}