二叉树算法题

一. 单值二叉树

单值二叉树 : . - 力扣（LeetCode）

思路 ：
1 . 如果根结点为空 ， return true

2 . 比较 根结点的值  与左/右子树的结点的值是否相等 

---> 比较之前，左右子树得保证不为空

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

二. 相同的树

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

思路 :

1 ) 两个树都为空 -----> return true

2 ) 仅一个树为空 -----> return false

3 ) 不为空 ---> 并且对应结点的值不相等 ----> return false

4 ) 继续遍历左右子树  ，判断对应的结点值是否相等

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/typedef struct TreeNode TreeNode;
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(q == NULL && p == NULL){return true;}   if(q == NULL || p == NULL){return false;}//p 和 q 都不为空if(q->val != p->val){return false;}return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

三 . 另一颗树的子树 

另一颗树的子树  : . - 力扣（LeetCode）

思路 : 基于第二题的思路来解决这道算法题

1 ） 当root 为空时 ， 直接return NULL ----> 因为此时不会出现与subRoot对应的结点相同

2 )   当root 与 subRoot 是相同的树的时候 ， return true

3 )   继续往下遍历左右子树 ， 是否存在与 subRoot 相同的树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/typedef struct TreeNode TreeNode;
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(q == NULL && p == NULL){return true;}if(q == NULL || p == NULL){return false;}//q 和 p 不为空if(q->val != p->val){return false;}return isSameTree(q->left,p->left) && isSameTree(q->right,p->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);
}

 四 . 二叉树的遍历

二叉树的遍历 : . - 力扣（LeetCode）

 typedef struct TreeNode TreeNode;//计算二叉树结点的个数int BTNodeSize(TreeNode* root){if(root == NULL){return 0;}return 1 + BTNodeSize(root->left) + BTNodeSize(root->right);}//前序遍历二叉树 -- 根左右void PreOrder(TreeNode* root , int* arr,int* pi){if(root == NULL){return;}arr[(*pi)++] = root->val;PreOrder(root->left,arr,pi);PreOrder(root->right,arr,pi);}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = BTNodeSize(root);int* arr= (int*)malloc(sizeof(int)*(*returnSize));int i = 0;PreOrder(root,arr,&i);return arr;
}

五 . 二叉树的构建及遍历 

二叉树的构建及遍历 : 二叉树遍历_牛客题霸_牛客网

#include <math.h>
#include <stdio.h>
//定义二叉树(结点)结构
typedef struct BinaryTreeNode{char data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//申请一块结点大小的空间
BTNode* BuyNode(char ch)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if(node == NULL){perror("malloc fail");exit(1);}node->data = ch;node->left = node->right = NULL;return node; 
}//根据前序遍历(根左右)创建二叉树
BTNode* CreateTree(char* arr,int* pi)
{if(arr[*pi]=='#'){(*pi)++;return NULL;}BTNode* root =  BuyNode(arr[*pi]);(*pi)++;root->left = CreateTree(arr, pi);root->right = CreateTree(arr, pi);return root;
}//中序遍历
void InOrder(BTNode* root)
{if(root == NULL){return;}InOrder(root->left);printf("%c ",root->data);InOrder(root->right);
}int main() {char arr[100];scanf("%s",arr);int i = 0;BTNode* root =  CreateTree(arr, &i);InOrder(root);return 0;
}