题号：100
难度：Easy
链接：https://leetcode.cn/problems/same-tree/comments/

思路

递归法想不出怎么做返回值，所以决定用栈来遍历结点。

初始时将两个root入栈，逐个出栈、判断、左右子结点入栈即可。

直到两个栈同时空，说明两个树相同。

代码

#include <stack>

using std::stack;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==nullptr&&q==nullptr) return true;
        if((p==nullptr&&q!=nullptr)||(p!=nullptr&&q==nullptr)) return false;
        stack<TreeNode*> s,t;
        s.push(p);t.push(q);
        while(!s.empty()||!t.empty()){ //有一个栈不空就继续
            if((s.empty()&&!t.empty())||(!s.empty()&&t.empty())) return false; //仅有一个栈空，说明不相同
            else{
                if((s.top()==nullptr&&t.top()!=nullptr)||(s.top()!=nullptr&&t.top()==nullptr)) return false; //栈顶元素仅有一个是null，说明不同
                else if(s.top()==nullptr&&t.top()==nullptr){
                    s.pop();t.pop(); //两个栈顶元素都null，弹出即可
                }
                else{
                    if(s.top()->val!=t.top()->val) return false; //两栈顶元素值不同，说明不同
                    else{ //两栈顶元素值相同
                        TreeNode* tp=s.top(),*tq=t.top(); //暂存栈顶
                        s.pop();t.pop(); //弹出栈顶
                        s.push(tp->right);s.push(tp->left); //左右子结点入栈，先右后左，如此左子节点先出栈
                        t.push(tq->right);t.push(tq->left);
                    }
                }
            }
        }
        return true; //while跳出，说明两栈均空，树相同
    }
};

提交结果

空间换时间。