【数据结构与算法】--二叉树OJ题

单值二叉树

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

示例 1：

输入：[1,1,1,1,1,null,1]
输出：true
示例 2：

输入：[2,2,2,5,2]
输出：false
 

提示：

给定树的节点数范围是 [1, 100]。
每个节点的值都是整数，范围为 [0, 99] 。

题解：这里注意每次进行递归的时候判断，父亲结点是否与孩子结点相等，若不相等可直接返回false。

bool isUnivalTree(struct TreeNode* root){
    if(root==NULL)
    {
        return true;
    }
    if(root->left!=NULL&&root->val!=(root->left)->val)
    {
        return false;
    }
    if(root->right!=NULL&&root->val!=(root->right)->val)
    {
        return false;
    }
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
 
}

 

 相同的树

相同的树https://leetcode.cn/problems/same-tree/

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

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

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104

 题解

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

二叉树的前序遍历

二叉树的前序遍历https://leetcode.cn/problems/binary-tree-preorder-traversal/

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

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
示例 4：

输入：root = [1,2]
输出：[1,2]
示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

题解

/**
 * 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().
 */
int TreeSize(struct TreeNode* root)
{
    if(root==NULL)
    {
        return 0;
    }
    return TreeSize(root->left)+TreeSize(root->right)+1;
}
void preorder(struct TreeNode* root,int* array,int* i)
{
    if(root==NULL)
    {
        return;
    }
 
    array[*i]=root->val;
    (*i)++;
    preorder(root->left,array,i);
    preorder(root->right,array,i);
 
 
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int n=TreeSize(root);
    int* array=(int*)malloc(sizeof(int)*n);
    *returnSize=n;
    int i=0;
    preorder(root,array,&i);
    return array;
 
}

 

另一棵树的子树

 另一棵树的子树https://leetcode.cn/problems/subtree-of-another-tree/

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

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

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

提示：

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-104 <= root.val <= 104
-104 <= subRoot.val <= 104

题解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
isSameSubtree(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 isSameSubtree(p->left,q->left)&&isSameSubtree(p->right,q->right);
 
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root==NULL)
    {
        return false;
    }
    if(isSameSubtree(root,subRoot))
    {
        return true;
    }
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
 
}