目录
- 1. 二叉树的前序遍历 (中,后序类似)
- 2. 二叉树的最大深度
- 3. 平衡二叉树
- 4. 二叉树遍历
1. 二叉树的前序遍历 (中,后序类似)
这道题的意思是对二叉树进行前序遍历,把每个结点的值都存入一个数组中,并且返回这个数组。
思路:
这题与我们平时写的二叉树前序遍历不同。需要我们自己开辟空间,但又由于二叉树结点个数未知,所以在开辟空间之前要先计算结点个数,根据结点个数开辟空间。最后再利用分治递归进行前序遍历。
代码实现如下:
注意:
(1) 结点个数的计算,数组空间的开辟;
(2) 递归时一般用子函数 _prevOrder 递归,而不是 preorderTraversal 原函数,不然会重复的开辟空间;
(3) 局部变量 i 一定要传地址,因为每一层递归函数都有一个 i ,下一层放的 i 是 i++之后的 i ,由于形参是实参的一份临时拷贝,若不传地址,就不会影响上一层函数中的 i ,就是加的不是同一个 i ;
(4) 输出型参数 returnSize ,目的是获取a数组有多大。
//前序遍历
void _prevOrder(struct TreeNode* root, int* a, int* pi)
{if (root == NULL)return;a[*pi] = root->val;(*pi)++;_prevOrder(root->left, a, pi);_prevOrder(root->right, a, pi);
}//由于不知道数组开多大的空间,所以要提前计算树的结点个数
int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {int size = TreeSize(root);//开辟数组空间int* a = (int*)malloc(sizeof(int) * size);int i = 0;_prevOrder(root, a, &i);*returnSize = size;return a;
}
2. 二叉树的最大深度
思路:
利用分治递归思想。若根节点为空,则深度为0;若非空,则先求左右子树的深度,我的深度 = 左右子树深度大的 + 1。
代码实现如下:
注意:
要先用两个变量记录计算好的左右子树的深度!不然运行时会超出时间限制。
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;
}
3. 平衡二叉树
平衡二叉树:是指该树所有节点的左右子树的深度相差不超过 1。
思路:
首先计算出每个节点的左右子树的深度,再计算它们的深度差是否超过1。
代码实现如下:
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);
}
4. 二叉树遍历
思路:
首先要根据输入的字符串构建一棵二叉树,再进行中序遍历。
代码实现如下:
注意:
局部变量 i 要传地址,不然递归调用时加的不是同一个 i。
//定义结点
typedef struct TreeNode
{struct TreeNode* left;struct TreeNode* right;char val;
}TNode;//创建二叉树
TNode* CreateTree(char* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}TNode* root = (TNode*)malloc(sizeof(TNode));if (root == NULL){perror("malloc fail!\n");exit(-1);}root->val = a[*pi];(*pi)++;root->left = CreateTree(a, pi);root->right = CreateTree(a, pi);return root;
}void InOrder(TNode* root)
{if (root == NULL)return;InOrder(root->left);printf("%c ", root->val);InOrder(root->right);
}int main() {char str[100] = { 0 };scanf("%s", str);int i = 0;//构建一棵树TNode* root = CreateTree(str, &i);InOrder(root);return 0;
}