LeetCode之相同的树（一百）

目录

题目

解题

方法一、递归法

题目

（原题链接：https://leetcode-cn.com/problems/same-tree/）

给定两个二叉树，编写一个函数来检验它们是否相同。

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

解题

方法一、递归法

分析：先比较当前节点，值相等再依次比较左子树和右子树，自然而然会想到递归的方法。

代码：（C++）

      /**
       * Definition for a binary tree node.
       * struct TreeNode {
       * int val;
       * TreeNode *left;
       * TreeNode *right;
       * TreeNode() : val(0), left(nullptr), right(nullptr) {}
       * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
       * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
       * };
       */
      class Solution {
      public:
      bool isSameTree(TreeNode* p, TreeNode* q) {
      if (!p && !q) return true;
      if (!p || !q) return false;//上一个判断过滤了都为空的情况，所以这里可以认为其中一个为空，另一个不为空
      return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
       }
      };
  
 

时间复杂度：O（logN）。

空间复杂度：O（1）。

执行结果：

如果有疑问，欢迎评论留言或者私信沟通！  

文章来源: liuzhen.blog.csdn.net，作者：Data-Mining，版权归原作者所有，如需转载，请联系作者。

原文链接：liuzhen.blog.csdn.net/article/details/107872370