原題地址：https://leetcode.com/problems/same-tree/description/

題目描述

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.

判斷兩棵樹是否相同。

思路

這一題的思路和上一題（題號(hào)617）挺像的。設(shè)了個(gè)bool變量areSame來表示是否相同，初始為true。同步遍歷兩棵樹，通過比較當(dāng)前節(jié)點(diǎn)的值和左右子節(jié)點(diǎn)的情況來決定接下來的操作。

代碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool areSame = true;
    
    void travelTogether(TreeNode* p,TreeNode* q){
        if(p->val != q->val){
            areSame = false;
            return ;
        }
        if(p->left !=NULL && q->left!=NULL){
            travelTogether(p->left,q->left);
        }else if(p->left ==NULL && q->left==NULL){
            //should not return directly here
        }else{
            areSame = false;
            return  ;
        }
        if(p->right!=NULL && q->right!=NULL){
            travelTogether(p->right,q->right);
        }else if(p->right==NULL && q->right==NULL){

        }else{
            areSame = false;
            return ;
        }
        
    }
    
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==NULL && q==NULL){
            return true;
        }
        if(p==NULL || q==NULL){
            return false;
        }
        travelTogether(p,q);
        return areSame;
    }
};

踩坑

遇到一個(gè)小問題。在travelTogether函數(shù)里判斷左子節(jié)點(diǎn)的分支的情況的時(shí)候（22行處），如果進(jìn)入到兩棵樹的當(dāng)前父節(jié)點(diǎn)都沒有左子節(jié)點(diǎn)的情況時(shí)，原本在那個(gè)分支里寫了個(gè)return語句直接返回了，但是這樣就導(dǎo)致不會(huì)執(zhí)行接下來對右子節(jié)點(diǎn)的操作。