二叉树oj题目

单值二叉树

解题思路

基本的解题思路就是比较根与左右两个节点的值是否相等。
在递归写法中，条件为归的条件，如果根为空，则返回真；根分别与左右两个孩子进行比较，不相同就返回假。最后再递左右两颗子树。

代码

bool isUnivalTree(struct TreeNode* root){
    
    if(root==NULL)
    return true;

    if(root->right&&root->val!=root->right->val)
    return false;

    if(root->left&&root->val!=root->left->val)
    return false;

   return isUnivalTree(root->left)&&isUnivalTree(root->right);

}

二叉树的最大深度

题目描述

解题思路

树的高度就是路径最长的那一个，找树的高度就是比较左右子树的高度，子树高度最大的加1就是该树的高度。写递归的时候要注意函数的参数以及是否有返回值的情况。

先写出口，当节点为空的时候返回0，
递：比较左右子树的高度
归：最大高度

代码

int maxDepth(struct TreeNode* root){
    
    if(root==NULL)
    return 0;

    int L=maxDepth(root->left)+1;
    int R=maxDepth(root->right)+1;

    return L>R?L:R;
}

相同的树

题目描述

解题思路

我们采取前序遍历的方法，先比较根节点，然后再比较左右子树。
只有根，左右子树都相同的时候才返回true。其余都返回false。

代码

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);
}

对称二叉树

题目描述

解题思路

除根节点外，左子树的左右节点与右子树的右左节点进行比较。
符合条件返回true，否则返回false。

代码

bool isSymmetryTree(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 isSymmetryTree(p->left,q->right)&&isSymmetryTree(p->right,q->left);
}

bool isSymmetric(struct TreeNode* root){
    
    return isSymmetryTree(root->left,root->right);
}

二叉树的前序遍历

题目描述

解题思路

先求出有多少个节点，然后再前序遍历，前序遍历是先遍历根节点，然后遍历左右孩子节点。当节点不为空的时候把数据储存在数组中。

代码

int TreeSize(struct TreeNode* root)
{
    
    if(root==NULL)
    return 0;
    return TreeSize(root->left)+TreeSize(root->right)+1;
}

void PreorderTree(struct TreeNode* root,int* a,int* n)
{
    
    if(root==NULL)
    return;
    a[*n]=root->val;
    ++*n;
    PreorderTree(root->left,a,n);
    PreorderTree(root->right,a,n);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    
    *returnSize=TreeSize(root);

    int* arr=(int*)malloc((*returnSize)*sizeof(int));
    int n=0;
    PreorderTree(root,arr,&n);
    return arr;
}

二叉树的中序遍历

题目描述

代码

int TreeSize(struct TreeNode* root)
{
    
    if(root==NULL)
    return 0;
    return TreeSize(root->left)+TreeSize(root->right)+1;
}

void  inorderTree(struct TreeNode* root,int* a,int* n)
{
    
    if(root==NULL)
    return;
    
    inorderTree(root->left,a,n);
    a[*n]=root->val;
    ++*n;
    inorderTree(root->right,a,n);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    
    *returnSize= TreeSize(root);
    int* arr=(int*)malloc((*returnSize)*sizeof(int));
    int n=0;
     inorderTree(root,arr,&n);
     return arr;
}

二叉树的后序遍历

题目描述

代码

 int TreeSize(struct TreeNode* root)
{
    
    if(root==NULL)
    return 0;
    return TreeSize(root->left)+TreeSize(root->right)+1;
}

void  postorderTree(struct TreeNode* root,int* a,int* n)
{
    
    if(root==NULL)
    return;
    
   postorderTree(root->left,a,n);
    
    postorderTree(root->right,a,n);
    a[*n]=root->val;
    ++*n;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    
    *returnSize= TreeSize(root);
    int* arr=(int*)malloc((*returnSize)*sizeof(int));
    int n=0;
     postorderTree(root,arr,&n);
     return arr;
}

另一棵树的子树

题目描述

解题思路

遍历root树，当root节点的值与subroot根节点的值相同的时候，就开始比较它们是否相同，如果相同就返回true，否则要继续遍历左右子树。左右子树遍历的结果要||。

代码

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);
    
}

二叉树遍历

题目描述

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char BTDataType;

typedef struct BinaryTreeNode
{
    
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;
BTNode* BuyNode(char ch)
{
    
    BTNode* newnode=(BTNode*)malloc(sizeof(BTNode));
    newnode->data=ch;
    newnode->left=newnode->right=NULL;
    return newnode;
}


BTNode* CreatTree(char* arr,int n,int* i)
{
    
   if(arr[*i]!='#'&&*i<n)
   {
    
       BTNode* root=BuyNode(arr[*i]);
       ++*i;
       root->left=CreatTree(arr, n, i);
       root->right=CreatTree(arr, n, i);
       return root;
   }
   else
    {
    
       ++*i;
       return NULL;
    }
    
}
void inorderTree(BTNode* root)
{
    
    if(root==NULL)
        return;
    inorderTree(root->left);
    printf("%c ",root->data);
    inorderTree(root->right);
}
int main()
{
    
    char arr[100];
    scanf("%s",arr);
    int len=strlen(arr);
    int i=0;
    BTNode* root=CreatTree(arr,len,&i);
    inorderTree(root);
    return 0;
}