title: Leetcode 100.相同的树
hidden: true
date: 2019-04-24 10:16:11
tags:

- C++
- Leetcode
- 递归
- 深度优先搜索

categories: Leetcode

mathjax: false

题目描述

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

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

示例 1:

输入:

   1         1
  / \       / \
 2   3     2   3

[1,2,3],   [1,2,3]

输出: true

示例 2:

输入:

   1          1
  /           \
 2             2

[1,2],     [1,null,2]

输出: false

示例 3:

输入:

   1         1
  / \       / \
 2   1     1   2

[1,2,1],   [1,1,2]

输出: false

题目分析

这道题可以用深度搜索来解决, 也可以用递归来解决.

源码(递归)

class Solution { // 递归方法
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL || q == NULL) { // 两个节点有一个为空
            return p == q;
        }else {
            return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
            // p节点的左子树和q节点左子树相等并且p节点的右子树和q节点的右子树相等
        }
    }
};

源码(深度优先搜索)

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q != NULL) return false; // 左树空树 右树非空树
        if(q == NULL && p != NULL) return false; // 右树空树 左树非空树
        if(p == NULL && q == NULL) return true;  // 同时为空树
        stack<TreeNode*> q1, q2; // 声明两个栈用来储存节点
        q1.push(p);
        q2.push(q);
        while(!q1.empty() && !q2.empty()) { // 有任意一个栈为空时停止循环
            TreeNode *cur1 = q1.top(), *cur2 = q2.top(); // 将栈首节点设为当前操作节点
            q1.pop(); // 将两个当前操作节点弹出
            q2.pop();
            if((cur1 == NULL && cur2 != NULL) || (cur1 != NULL && cur2 == NULL)) return false;
            // 判断是否只有一个节点为空
            if(cur1 != NULL){ // 如果两个节点都不为空则对比两个节点值, 如果相等则将其子节点压入栈
                if(cur1->val != cur2->val) return false;
                q1.push(cur1->left);
                q1.push(cur1->right);
                q2.push(cur2->left);
                q2.push(cur2->right);
            }
        }
        return true;
    }
};