# Leetcode [No. 100] Same Tree (EASY) 解題心得

+ 2024/02/26 Daily Challenge

## 題目

https://leetcode.com/problems/same-tree/description/

## 思路

這個問題其實就是判斷兩棵樹長的相不相同，可以透過比較現在這個node&&left&&right來做決定。

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return dfs(p,q);        
    }
    bool dfs(TreeNode* p, TreeNode* q)
    {
        if(p == q) // nullptr
        {
            return true;
        }
        else if (p!=nullptr && q!=nullptr && p->val == q->val)
        {
            return dfs(p->left, q->left) && dfs(p->right, q->right);
        }
        else
        {
            return false;
        }
    }
};

### 解法分析
+ time complexity: O(lgn)

### 執行結果

## 改良

+ 直接把solution用成recursive的方法，主要會去recursive每一個節點，並且以自己為主，再去判斷左右的node是否相同。

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q)
        {
            return true;
        }
        bool same = false;
        if(p != nullptr && q != nullptr && p->val == q->val)
        {
            same = true;
        }
        return same && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);   
    }  
};

### 執行結果


## 2024/02/26 改良

與上一版差不多，只是省了一個變數

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == q) return true; // both of them are nullptr
        if(p!= nullptr && q!= nullptr)
            return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        else
            return false;
    }
};


---

## 三訪

+ 2025/04/27 第三次遇到，一次過。發現寫得跟上一版差不多。

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == q) return true; // both null
        if (p && q) {
            if (p->val != q->val) {
                return false;
            }
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        }
        else {
            // one is null and other not
            return false;
        }

    }
};