二叉樹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;
}