二叉树OJ题（1）

1 单值二叉树

👉OJ链接

思路分析

• 分治：自己、左子树、右子树
• 结束条件：遇到空，就返回到所调用的函数
• 每一个都是自己和自己左右子树进行比较，如果不相等且不为空，返回false。如果相等，继续递归。（先检查自己，再检查左子树，再检查右子树）

代码实现

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

2 相同的树

👉OJ链接

思路分析

• 分治思想：根和根比较相同----->左子树和左子树比较&&右子树和右子树比较 
• 都是对应的节点和节点进行比较
• 两个节点中数字相等，则继续往下比较（遍历比较）。不相等则返回false

  ---

  有以下三种情况，要都考虑到，防止系统崩溃。

• 两棵树的根节点都是NULL
• 两棵树的一个根节点为NULL，另外一个不为NULL
• 两棵树根节点都不为NULL

•  注意：必须左右两边子树都相等才可返回true，只是一边并不能返回true。

代码实现

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    //两个都为空
    if(p == NULL && q == NULL)
    {
        return true;
    }

    //其中一个为空，另一个不为空
    if(p == NULL || q == NULL)
    {
        return false;
    }

    //两个都不为NULL且不相等
    if(p->val != q->val)
    {
        return false;
    }

    return isSameTree(p->left,q->left) 
        && isSameTree(p->right,q->right);
}

递归展开图

3 二叉树的前序遍历

OJ链接

思路分析

开辟一个数组，然后把前序遍历树的顺序放入数组即可。  

• 把根的val放入数组第一个元素
• 接着放入左右（递归下去）

代码实现

int TreeSize(struct TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    return TreeSize(root->left)+TreeSize(root->right)+1;
}
 
int *preorder(struct TreeNode* root,int*a,int* pi)
{
    if(root == NULL)
    {
        return NULL;
    }
    a[(*pi)++]=root->val;
    preorder(root->left,a,pi);
    preorder(root->right,a,pi);
    return a;
}
 
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int treesize=TreeSize(root);
    //注意这里传地址
    *returnSize=treesize;
    int*a=(int*)malloc(sizeof(struct TreeNode)*treesize);
    int i=0;
    a=preorder(root,a,&i);
    i=0;
    return a;
}

注意事项

• 改变形式参数必须要用指针，形参的修改不影响实参，形参是实参的一份临时拷贝。

• 一定要注意这里要是 int* pi，pi在不同函数里调用的时候是形式参数，使用时需要用指针才行。（也可以使用全局变量，int i。但是一定要在preorderTraversal函数里调用preorder函数递归前将i置零，因为外界可能会多次调用preorderTraversal函数，就会造成越界！）

• 👇错误案例