3.3怎么求第k层节点的个数？
核心思路：递归返回第k-1层左右结点相加的值
int BTreekLeafSize(BTNode* root, int k) { assert(k >= 1); if (root == NULL) return 0; if (k == 1) return 1; return BTreekLeafSize(root->left, k - 1) + BTreekLeafSize(root->right, k - 1);//返回左结点和右结点的上一层 }
3.4求一棵树的高度
思想：比较左右子树的高度，并且返回高度大的加一（原因：加根结点）
int BTreeDepth(BTNode* root) { if (root == NULL) return 0; int leftDepth = BTreeDepth(root->left); int rightDepth = BTreeDepth(root->right); return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; }
3.5二叉树查找值为x的结点
思路：用前序遍历去递归搜索，先搜左子树，如果左子树没有，就返回一个NULL到根结点，然后根结点再递归搜索右树，如果右树有就返回那个点的值。
BTNode* BTreeFind(BTNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->data == x) return root; //用前序遍历的思想 BTNode* ret1 = BTreeFind(root->left, x);//先去递归左树 if (ret1)//如果左边返回的不是NULL { return ret1; } BTNode* ret2 = BTreeFind(root->right, x); if (ret2) { return ret2; } return NULL; }
3.6判断一棵树是不是完全二叉树
思路：就是把空也当作二叉树的节点放进去，然后运用层序遍历，
如果在遍历的中间过程中遇到空就说明不是完全二叉树。
队列不能直接像数组一样遍历
//判断一棵树是不是完全二叉树 bool BinaryTreeComplete(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root);//先插入根节点 } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q);//会等于队头第一个数据的值 QueuePop(&q); if (front == NULL) { break; } QueuePush(&q, front->left); QueuePush(&q, front->right); } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q);//会等于队头第一个数据的值 QueuePop(&q); if (front)//如果出到非空，那么就不是完全二叉树 { return false; } } return true; }
四、二叉树oj题
bool isUnivalTree(struct TreeNode* root) { if(root == NULL) return true; if(root->left && root->left->val != root->val)//如果左结点不为空，且左树结点的值不等于根的值，返回false return false; if(root->right && root->right->val != root->val)//如果右结点不为空，且右树结点的值不等于根的值，返回false return false; return isUnivalTree(root->left) && isUnivalTree(root->right);//递归判断 }
思路：先判断两棵树是不是都是空树，再判断如果一个为空一个不为空，最后递归
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); }
注意：这里的判断不能写成p->left->val != q->left->val
会报错
思路：写一个辅助函数，舍弃根结点，判断左边这个树是否与右边这个树对称
bool isSymmetricTree(struct TreeNode* p, struct TreeNode* q) { //如果root的左和右节点都为空 if(p == NULL && q == NULL) return true; //如果一个为空一个不为空 if(p == NULL || q == NULL) return false; return p->val == q->val && isSymmetricTree(p->left, q->right) && isSymmetricTree(p->right, q->left); } bool isSymmetric(struct TreeNode* root) { if(root == NULL) return true; return isSymmetricTree(root->left, root->right); }
4、144. 二叉树的前序遍历 - 力扣（LeetCode）
题目意思解释：Note: The returned array must be malloced, assume caller calls free().
这句话的意思是数组要malloc， 然后caller系统会帮你free掉
int* returnSize的意思是返回结点的个数
代码如下所示：
int TreeSize(struct TreeNode* root)//计算树的结点个数，方便malloc空间 { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } //定义一个子函数去完成前序遍历 void _preorder(struct TreeNode* root, int* a,int *pi) { if(root == NULL) return; a[(*pi) ++] = root->val;//控一下优先级*的优先级低于++，所以要加（） _preorder(root->left, a, pi); _preorder(root->right, a, pi); } int* preorderTraversal(struct TreeNode* root, int* returnSize)//int*returnSize是输出型参数 { int size = TreeSize(root); //不考虑动态扩容 int* a = malloc(sizeof(int)*size); int i = 0; *returnSize = size; _preorder(root, a, &i); return a; }
因为之后的二叉树中序以及后序遍历思路差不多，所以如果读者有兴趣可以根据这个思路去做。
思路：左边树中每一个子树都比较isSameTree
遍历左边的每个节点，做子树的根，跟右边的子树都比较一下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; if(isSameTree(root, subRoot)) { return true; } return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot); }
6.二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
先序遍历字符串构造的二叉树（前序）
递归、分治的思想
#include<stdio.h> #include<string.h> //构造结构体 typedef struct BinaryTreeNode { char data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; //造树 BTNode* CreatTree(char* a, int* pi) { if(a[*pi] == '#') { (*pi)++; return NULL; } BTNode* root = (BTNode*)malloc(sizeof(BTNode)); root->data = a[(*pi)++]; root->left = CreatTree(a, pi); root->right = CreatTree(a, pi); return root; } void InOrder(BTNode* root) { if(root == NULL)//这里root直接等于NULL判断便可，不需要‘# { return; } InOrder(root->left); printf("%c ", root->data); InOrder(root->right); } //main函数部分 int main () { char a[101]; scanf("%s", a); int i = 0; BTNode* tree = CreatTree(a, &i); InOrder(tree); return 0; }
