leetcode Same Tree

题目链接

same-tree

题目描述(Description)

Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

相同树

给两个二叉树，写一个函数检测它们是否相同。

两个二叉树如果结构和结点数值都相同则判定两树相同。

分析(Analysis)

• 两树相同的条件比较难，逆向思维，找两树不相同的条件。

• 结构不同：一个有左（右）子，另一个没有左（右）子；

• 对应结点数值不同。

• 递归左右子树。

代码(Code)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if(!p&&!q)//两树都为空
            return true;
        if((!p&&q)||(p&&!q)||(p->val!=q->val))//两树不相等的条件
            return false;
        bool left=isSameTree(p->left,q->left);//递归左子树
        bool right=isSameTree(p->right,q->right);//递归右子树
        return left&&right;
    }
};