Leetcode 100.same tree

原题地址：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.

判断两棵树是否相同。

思路

这一题的思路和上一题（题号617）挺像的。设了个bool变量areSame来表示是否相同，初始为true。同步遍历两棵树，通过比较当前节点的值和左右子节点的情况来决定接下来的操作。

代码

/**
 * 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;
    }
};

踩坑

遇到一个小问题。在travelTogether函数里判断左子节点的分支的情况的时候（22行处），如果进入到两棵树的当前父节点都没有左子节点的情况时，原本在那个分支里写了个return语句直接返回了，但是这样就导致不会执行接下来对右子节点的操作。