100 same tree

1. 题目描述

两个二叉树比较是否相同，相同意味着树的结构相同，树的节点值相同

2. 题解

本质是二叉树的遍历，而二叉树的遍历常用到递归，所以这道题的本质还是递归的应用。

使用全局变量的递归算法

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

真正意义上的递归

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if (p == NULL || q == NULL) return (p == q);
        return (p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right));
    }
};

3. 视频讲解

4. 总结

二叉树分为左右子树和根节点。而二叉树相同，即左右子树相同且根节点相同。

100 same tree

原文：https://www.cnblogs.com/MartinTai/p/14669360.html