100.相同的树 (Easy)*

题目描述*

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例*

输入:

           1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

代码*

同时遍历两个树，比较即可，此处采用的是中序遍历，即当前节点入栈，访问左节点。

中序

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        TreeNode *curp = p;
        TreeNode *curq = q;
        stack<TreeNode*> pStack;
        stack<TreeNode*> qStack;
        while(curp != nullptr && curq != nullptr || !pStack.empty() && !qStack.empty()) {
            while(curp != nullptr) {
                pStack.push(curp);
                curp = curp->left;
            }
            while(curq != nullptr) {
                qStack.push(curq);
                curq = curq->left;
            }
            curp = pStack.top();
            curq = qStack.top();
            pStack.pop();
            qStack.pop();
            if(curp->val != curq->val) {
                return false;
            }
            curp = curp->right;
            curq = curq->right;
        }
        if(!(curq == nullptr && curp == nullptr) || !(qStack.empty() && pStack.empty())) {
            return false;
        }
        return true;
    }
};

最后更新: July 23, 2022