二叉树知识回顾——【树】之二叉树(C语言)(含图解)_半生瓜のblog-CSDN博客
二叉树的前序遍历
144. 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)
本题中，对于C++或者Java等语言，返回的是它们的数据结构库里面的数据结构，而C语言没有，这也就是如果用C语言往后通吃数据结构会困难的原因。
注意本体的传参，操作的是不是一个数。
/**
* 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
本质上用的后序遍历，先求左，后求右边，再求自己。
图示
/**
* 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)
/**
* 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);
}
