二叉树oj题目

二叉树

单值二叉树

解题思路

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

代码

bool isUnivalTree(structTreeNode* 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;returnisUnivalTree(root->left)&&isUnivalTree(root->right);}

二叉树的最大深度

题目描述

解题思路

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

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

代码

intmaxDepth(structTreeNode* root){if(root==NULL)return0;int L=maxDepth(root->left)+1;int R=maxDepth(root->right)+1;return L>R?L:R;}

相同的树

题目描述

解题思路

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

代码

bool isSameTree(structTreeNode* p,structTreeNode* q){if(p==NULL&&q==NULL)return true;if(p==NULL||q==NULL)return false;if(p->val!=q->val)return false;returnisSameTree(p->left,q->left)&&isSameTree(p->right,q->right);}

对称二叉树

题目描述

解题思路

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

代码

bool isSymmetryTree(structTreeNode* p,structTreeNode* q){if(p==NULL&&q==NULL)return true;if(p==NULL||q==NULL)return false;if(p->val!=q->val)return false;returnisSymmetryTree(p->left,q->right)&&isSymmetryTree(p->right,q->left);}

bool isSymmetric(structTreeNode* root){returnisSymmetryTree(root->left,root->right);}

二叉树的前序遍历

题目描述

解题思路

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

代码

intTreeSize(structTreeNode* root){if(root==NULL)return0;returnTreeSize(root->left)+TreeSize(root->right)+1;}voidPreorderTree(structTreeNode* 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(structTreeNode* root,int* returnSize){*returnSize=TreeSize(root);int* arr=(int*)malloc((*returnSize)*sizeof(int));int n=0;PreorderTree(root,arr,&n);return arr;}

二叉树的中序遍历

题目描述

代码

intTreeSize(structTreeNode* root){if(root==NULL)return0;returnTreeSize(root->left)+TreeSize(root->right)+1;}voidinorderTree(structTreeNode* 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(structTreeNode* root,int* returnSize){*returnSize=TreeSize(root);int* arr=(int*)malloc((*returnSize)*sizeof(int));int n=0;inorderTree(root,arr,&n);return arr;}

二叉树的后序遍历

题目描述

代码

intTreeSize(structTreeNode* root){if(root==NULL)return0;returnTreeSize(root->left)+TreeSize(root->right)+1;}voidpostorderTree(structTreeNode* 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(structTreeNode* 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(structTreeNode* p,structTreeNode* q){if(p==NULL&&q==NULL)return true;if(p==NULL||q==NULL)return false;if(p->val!=q->val)return false;returnisSameTree(p->left,q->left)&&isSameTree(p->right,q->right);}
bool isSubtree(structTreeNode* root,structTreeNode* subRoot){if(root==NULL)return false;if(root->val==subRoot->val)if(isSameTree(root,subRoot))return true;returnisSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);}

二叉树遍历

题目描述

代码

#include<stdio.h>#include<stdlib.h>#include<string.h>typedefchar BTDataType;typedefstructBinaryTreeNode{structBinaryTreeNode* left;structBinaryTreeNode* 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;returnNULL;}}voidinorderTree(BTNode* root){if(root==NULL)return;inorderTree(root->left);printf("%c ",root->data);inorderTree(root->right);}intmain(){char arr[100];scanf("%s",arr);int len=strlen(arr);int i=0;
    BTNode* root=CreatTree(arr,len,&i);inorderTree(root);return0;}