餐饮技术支持东莞网站建设,设计类网站开发策划书,浙江十大外贸公司,网页微信版二维码过期怎么办目录 1. 二叉树的前序遍历 (中#xff0c;后序类似)2. 二叉树的最大深度3. 平衡二叉树4. 二叉树遍历 1. 二叉树的前序遍历 (中#xff0c;后序类似) 这道题的意思是对二叉树进行前序遍历#xff0c;把每个结点的值都存入一个数组中#xff0c;并且返回这个数组。
思路后序类似)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;
}
