C语言详解判断相同树案例分析

题目难度：简单

一、题目描述

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

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

LeetCode链接：相同的树

二、解题思路

核心思路：

先比较两颗二叉树的根节点

• 如果「都为空」，则返回 true，说明两树相同。
• 如果「一个为空一个不为空」，说明这两颗树不相同，则返回 false。
• 如果「都不为空，但节点值不相同」，说明这两颗树不相同，则返回 false。
• 经过 1 和 2 和 3 的判断，说明根节点「都不为空，但节点值相同」，则当前节点相同。我们继续递归遍历，比较它的左子树和右子树的根节点。

递归过程演示：

依次比较两颗二叉树中「当前树(1、2、3、4、5、6)的根节点」是否相等，这样每个节点都被比较了一次。

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     struct TreeNode *left;
*     struct TreeNode *right;
* };
*/
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
  // 1. 先比较两颗树的根节点
  // 都为空，返回true，说明满足相同的树的条件
  if(p == NULL && q == NULL)
  {
      return true;
  }
  // 一个为空一个不为空，返回false
  if(p == NULL || q == NULL)
  {
      return false;
  }
  // 都不为空，但节点值不相等，返回false
  if(p->val != q->val)
  {
      return false;
  }
  // 2. 经过前面的if的判断，既然运行到这里了，说明当前节点相等
  // 则继续比较左子树和右子树的根节点
  return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

时间复杂度：假设两棵树都有 n 个节点，最多比较 n 次，所以为 O ( N ) O(N) O(N)

空间复杂度：往下递归会开辟栈帧空间，函数返回时会还给操作系统，所以「空间复杂度」和「递归的最大深度」有关，最坏情况下，「递归的最大深度」就是有 n 的节点二叉树的最大深度，所以为 O ( N ) O(N) O(N)

• 最大深度： 此树为单边树，则深度为 n，最多向下创建 n 个栈帧，因为栈帧会边用边销毁
• 最小深度： 此树为完全二叉树/满二叉树，则深度为 log2(N+1)

关于C语言详解判断相同树案例分析的文章就介绍至此，更多相关C语言判断相同树内容请搜索编程宝库以前的文章，希望以后支持编程宝库！

 一、函数指针1.概念函数指针：首先它是一个指针，一个指向函数的指针，在内存空间中存放的是函数的地址；请看示例：int main(){int a = 10;int*pa = &a;char c ...