此篇皆为leetcode、牛客中的简单题型和二叉树基础操作，无需做过多讲解，仅付最优解。有需要的小伙伴直接私信我~
目录
1.二叉树的节点个数
2.二叉树叶子节点个数
3.二叉树第K层节点个数
4.查找值为X的节点
5.leetcode——二叉树的最大深度
6.leetcode——单值二叉树
7.leetcode——相同的树
8.二叉树的前序遍历
9.二叉树的中序遍历
10.二叉树的后序遍历
11.二叉树的层序遍历
12.leetcode——另一棵树的子树
13.二叉树的构建及遍历
14.leetcode——对称二叉树
正文
1.二叉树的节点个数
int BinaryTreeSize(BTNode* root) { return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; }
2.二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); }
3.二叉树第K层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k) { if (root == NULL) return 0; if (k == 1) return 1; return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); }
4.查找值为X的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType data) { if (root == NULL) return NULL; if (root->data == data) return root; BTNode* ret1 = BinaryTreeFind(root->left, data); if (ret1) return ret1; BTNode* ret2 = BinaryTreeFind(root->right, data); if (ret2) return ret2; return NULL; }
5.leetcode——二叉树的最大深度
int maxDepth(struct TreeNode* root) { if (root == NULL) return 0; int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; }
6.leetcode——单值二叉树
bool isUnivalTree(struct TreeNode* root) { if (root == NULL) { return true; } if (root->left && root->val != root->left->val) return false; if (root->right && root->val != root->right->val) return false; return isUnivalTree(root->left) && isUnivalTree(root->right); }
7.leetcode——相同的树
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); }
8.二叉树的前序遍历
void PrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->data);//前序在前 PrevOrder(root->left); PrevOrder(root->right); }
9.二叉树的中序遍历
void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data);//中序在中 InOrder(root->right); }
10.二叉树的后序遍历
void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data);//后序在后 }
11.二叉树的层序遍历
//需自己实现队列的数据结构 void BinaryTreeLevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root) QueuePush(&q, root); else return; while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); printf("%d ", front->data); QueuePop(&q); if(front->left) QueuePush(&q, front->left); if(front->right) QueuePush(&q, front->right); } printf("\n"); QueueDestroy(&q); }
12.leetcode——另一棵树的子树
//判断两树是否相同（复用“相同的树”解题代码） 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 false; if(isSametree(root,subRoot)) return true; return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot); }
13.二叉树的构建及遍历
#include <stdio.h> #include <stdlib.h> struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; struct TreeNode* rebuildTree(char* str,int* pi) { if(str[*pi] == '#') { (*pi)++; return NULL; } struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); root->val = str[(*pi)++]; root->left = rebuildTree(str,pi); root->right = rebuildTree(str,pi); return root; } void TreeDestory(struct TreeNode* root) { if(root==NULL) return; TreeDestory(root->left); TreeDestory(root->right); free(root); } void InOrder(struct TreeNode* root) { if (root == NULL) { return; } InOrder(root->left); printf("%c ", root->val); InOrder(root->right); } int main() { char str[100]; scanf("%s",str); int i=0; struct TreeNode* root = rebuildTree(str,&i); InOrder(root); TreeDestory(root); return 0; }
14.leetcode——对称二叉树
bool _isSymmetric(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 _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left); } bool isSymmetric(struct TreeNode* root) { return root == NULL ? 0 : _isSymmetric(root->left, root->right); }
