【数据结构】二叉树经典习题

965. 单值二叉树

思路：

1.若树为空，则返回true，因为并不违反规则。

2.将根结点和左子树右子树的值做比较，若不相等就返回false.

3.递归实现先序遍历即可，即左子树比完再比右子树，且都得相等。

 

bool isUnivalTree(struct TreeNode* root){
    //先序遍历
    if(root == NULL)
        return true;
        //判断==并没有多大的用处，判断相反可快速结束递归。
    if(root->left && root->val != root->left->val)//1.判断节点是否存在，2.判断值是否不相等。
        return false;
    if(root->right && root->val != root->right->val)
        return false;
    return isUnivalTree(root->left) && isUnivalTree(root->right);//左树 右树都得同时满足才可返回真
 
}

100. 相同的树

在两棵树的比较，就是看对应节点是否存在且相等。

思路：1.若两棵树都为空，则返回true。

2.若两棵树对应节点有缺失，则返回false

3.递归，前序遍历即可。

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 _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 true;
    //调用相同树的代码
    return _isSameTree(root->left,root->right);
 
}

二叉树的前序遍历

复习：前序遍历：根 - 左子树 - 右子树

总之还是递归分治的思想，但是，这道题又有点不同。

这道题要自己申请一个数组空间来存储数据，使用静态的数组会因为函数栈帧的缘故，当函数出了作用域时，就会被销毁，返回的值可能就根本”不存在“。而static修饰的静态局部变量，多次调用，就会出现数据覆盖的问题，最优解就是：在堆上开辟空间，那开多大的空间？

我们可以先遍历一遍二叉树，获得二叉树的节点个数，相应的代码及思路已经在之前的博客中提及过了。

思路：1.先序遍历的思想

2.递归求节点的个数。

2.动态开辟数组。

 

 int BTreeSize(struct TreeNode* root)
{
    return root == NULL? 0:BTreeSize(root->left)+BTreeSize(root->right)+1;
}
void _preorder(struct TreeNode* root,int* a,int* pi)
{
    if(root == NULL)
        return ;
    a[(*pi)++] = root->val;
 
    _preorder(root->left,a,pi);
    _preorder(root->right,a,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    //确定树的大小
    *returnSize = BTreeSize(root);
    int* a = (int*)malloc(sizeof(int)*(*returnSize));
 
    int i =0;
    _preorder(root,a,&i);
    return a;
}

二叉树的后序遍历

后序遍历：左子树 - 右子树 - 根

思路与上面的前序遍历一致

 

int BTreeSize(struct TreeNode* root)
{
    return root == NULL? 0:BTreeSize(root->left)+BTreeSize(root->right)+1;
}
void _preorder(struct TreeNode* root,int* a,int* pi)
{
    if(root == NULL)
        return ;
 
    _preorder(root->left,a,pi);
    _preorder(root->right,a,pi);
    a[(*pi)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = BTreeSize(root);
    int* a = (int*)malloc(sizeof(int)*(*returnSize));
 
    int i =0;
    _preorder(root,a,&i);
    return a;
 
}

二叉树的中序遍历

int BTreeSize(struct TreeNode* root)
{
    return root == NULL? 0:BTreeSize(root->left)+BTreeSize(root->right)+1;
}
void _preorder(struct TreeNode* root,int* a,int* pi)
{
    if(root == NULL)
        return ;
 
    _preorder(root->left,a,pi);
    a[(*pi)++] = root->val;
    _preorder(root->right,a,pi);
    
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = BTreeSize(root);
    int* a = (int*)malloc(sizeof(int)*(*returnSize));
 
    int i =0;
    _preorder(root,a,&i);
    return a;
}

另一棵树的子树

本质上就是寻找子树的问题，当大树的一个小树和所给定的小树的结构和值完全相等时,返回true

考虑调用判断两个数是否相同的函数代码，采用分治的思想，先跑完左子树寻找，再跑右子树寻找，期间若找到了，就直接返回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 && subRoot == NULL)
        return true;
    if(root == NULL || subRoot == NULL)
        return false;
    //判断其是否为相同的树,找完左树找右树
    return _isSameTree(root,subRoot) || isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

二叉树遍历

思路：1）建树，递归分治建树。

2）传递参数时，要传递指针，传值调用，传递的是形参，形参的改变不会影响实参，所以递归时就会出错。

3）中序遍历，左子树 - 根 - 右子树

#include<stdio.h>
#include<stdlib.h>
typedef struct BTreeNode
{
    char data;
    struct BTreeNode* left;
    struct BTreeNode* right;
}BTNode;
BTNode* CreatTree(char *a, int *pi)//这里必须传递指针 pi
{
    //递归方式创建树，那么就必须传址调用，而不是传值调用。
    //如果是‘#’就返回NULL，同时找数组下一位
    if(a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    //创建树
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    root->data = a[(*pi)++];
    root->left = CreatTree(a, pi);
    root->right = CreatTree(a, pi);
    return root;
}
void InOrder(BTNode* root)
{
    if(root == NULL)
        return;
    InOrder(root->left);
    printf("%c ",root->data);
    InOrder(root->right);
}
int main()
{
    char a[100];
    scanf("%s",a);
    //创建树
    int i = 0;
    BTNode* Tree = CreatTree(a,&i);
    InOrder(Tree);
    return 0;
}