【数据结构】二叉树--OJ练习题

目录

1 单值二叉树

2 相同的树

3 另一颗树的子树

4 二叉树的前序遍历

5 二叉树的最大深度

6 对称二叉树

7 二叉树遍历

---

1 单值二叉树

965. 单值二叉树 - 力扣（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);}

2 相同的树

100. 相同的树 - 力扣（LeetCode）

 

/*
* Definition for a binary tree node.
* struct TreeNode {*int val;*struct TreeNode* left;*struct TreeNode* 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);}

3 另一颗树的子树

572. 另一棵树的子树 - 力扣（LeetCode）

 

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *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);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {if (root == NULL){return false;}if (root->val == subRoot->val){if (isSametree(root, subRoot)){return true;}}return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);}

4 二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode）

/*** 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 PrevOrder(struct TreeNode* root, int* a, int* i)//这里的i 之所以传指针是因为递归的时候要保存上一次i的值 
{if (root == NULL){return;}a[*i] = root->val;(*i)++;PrevOrder(root->left, a, i);PrevOrder(root->right, a, i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {int n = TreeSize(root);int* a = (int*)malloc(sizeof(int) * n);int j = 0;PrevOrder(root, a, &j);//这里j取地址*returnSize = n;return a;
}

5 二叉树的最大深度

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

/*** 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 ret1 = maxDepth(root->left);int ret2 = maxDepth(root->right);return (fmax(ret1, ret2) + 1);}

6 对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *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->right) && isSameTree(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root) {if (root == NULL){return NULL;}return isSameTree(root->left, root->right);
}

7 二叉树遍历

二叉树遍历_牛客题霸_牛客网

 

#include <stdio.h>
#include<stdlib.h>
typedef struct BianryTreeNode
{struct BianryTreeNode* left;struct BianryTreeNode* right;char val;
}BTNode;BTNode* CreatTree(char* a, int* i)//前序遍历
{if (a[*i] == '#'){(*i)++;return  NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->val = a[*i];(*i)++;root->left = CreatTree(a, i);root->right = CreatTree(a, i);return root;
}void PrintInOrder(BTNode* root)//中序遍历
{if (root == NULL){return;}PrintInOrder(root->left);printf("%c ", root->val);PrintInOrder(root->right);
}
int main() {char arr[100];scanf("%s", arr);int i = 0;BTNode* root = CreatTree(arr, &i);PrintInOrder(root);return 0;
}

本节对二叉树的一些常规OJ题目进行了代码实现和讲解, 虽然图解很少, 但是大家根据代码和注释也可以很好理解,也可以自己画一画递归展开图.本节对二叉树链式结构的基础要求很高, 大家如果基础不好,可以先看看我之前的博客.

继续加油!