【初阶数据结构篇】二叉树算法题

文章目录

二叉树算法题
- 前言
- 单值二叉树
- 相同的树
- 对称二叉树
- 另一棵树的子树
- 二叉树的前序遍历

二叉树算法题

前言

本篇的算法题涉及到链式结构二叉树的实现方法
可参考：
二叉链实现方法上篇
二叉链实现方法下篇

单值二叉树

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。

在这里插入图片描述

拿到根节点，和左右孩子比较
- 左孩子不为空就判断是否相等，右孩子同理
以相同方式递归左右子树
结束条件
- root为空，不影响，返回true
- 若不相等直接返回false

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

相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

在这里插入图片描述

如果两个二叉树都为空，则两个二叉树相同。
如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *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->left) && isSameTree(p->right, q->right);
}

对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。（root不为空）

在这里插入图片描述

二叉树是否对称，即左右子树是否对称
把左右子树当做单独的两棵树来比较
在上面一道相同的树中，我们是通过同时递归两棵树的左子树判断是否相等，对右子树同理
而本题则是对称，即判断一棵树的左子树和右子树（以及右子树和左子树）是否相等
所以我们同时递归一棵树的左子树和另一棵树的右子树（以及前者的右子树和后者左子树）即可
将上面代码略微修改即可

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

另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树

1722326846642)

思路很简单，依次递推，到每个结点时判断即可
- 在左子树或者右子树找到了直接返回就行，注意是||不是&&
对于每个结点都当作根节点，来判断以这个结点为根节点的树和subRoot是否相等
判断相等还是使用上面的isSameTree方法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *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->left) && isSameTree(p->right, q->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);
}

二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的前序遍历。

在这里插入图片描述

本题的特殊之处在于它的返回值是一个数组，所以我们需要先为数组动态开辟一块空间
第一步：计算二叉树结点个数
第二步：前序遍历并依次插入
- 自己写一个前序遍历函数
- 在插入时，使用传址调用的方式。不能创建全局变量，否则只能调用一次这个函数

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/typedef struct TreeNode TreeNode;int TreeSize(TreeNode* root){if(root==NULL)return 0;return 1+TreeSize(root->left)+TreeSize(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=TreeSize(root);int* arr=(int*)malloc(sizeof(int)*(*returnSize));int i=0;Preorder(root,arr,&i);return arr;
}