100. 相同的树

• 题目要求
  给出两二叉树，询问这两棵树是否完全相同，输出true或者false

• 题目思路(我的，不知道是否可行，目前仍然是wa，QAQ)

  • 先知条件：如果已知先序遍历(\(DLR\))和中序遍历(\(LDR\))或者后序遍历(\(LRD\))和中序遍历(\(LDR\))
  • 那么我通过\(4\)个\(dfs\)深度遍历两棵树\(TreeNode\) \(p\),\(TreeNode\) \(q\)
    分别得到相应的中序遍历和先(后)序遍历，最后再两个\(for\)循环进行遍历判断是否相同
  • 代码如下

    /**
     * Definition for a binary tree node.
     * 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:
        vector<int> lrp[2],lpr[2];
        void init(){
            for(int i=0;i<2;i++){
                lrp[i].clear();
                lpr[i].clear();
            }
        }
        void dfs_lrp1(TreeNode* root){
            if(!root)return;
            dfs_lrp1(root->left);
            dfs_lrp1(root->right);
            lrp[0].push_back(root->val);
        }
        void dfs_lrp2(TreeNode* root){
            if(!root)return;
            dfs_lrp2(root->left);
            dfs_lrp2(root->right);
            lrp[1].push_back(root->val);
        }
        void dfs_lpr1(TreeNode* root){
            if(!root)return;
            dfs_lpr1(root->left);
            lpr[0].push_back(root->val);
            dfs_lpr1(root->right);
        }
        void dfs_lpr2(TreeNode* root){
            if(!root)return;
            dfs_lpr2(root->left);
            lpr[1].push_back(root->val);
            dfs_lpr2(root->right);
        }
        bool isSameTree(TreeNode* p, TreeNode* q) {
            init();
            dfs_lrp1(p);
            dfs_lpr1(p);
            dfs_lpr2(q);
            dfs_lrp2(q);
            int f,ff;
            f=ff=1;
            if(lrp[0].size()==lrp[1].size()&&lpr[0].size()==lpr[1].size()&&p->size()==q->size()){
                for(int i=0;i<lrp[0].size();i++){
                if(lrp[0][i]!=lrp[1][i]){
                    f=0;
                    break;
                    }
                }
                for(int i=0;i<lpr[0].size();i++){
                    if(lpr[0][i]!=lpr[1][i]){
                        ff=0;
                        break;
                    }
                }
            }
            else{
                f=0;
            }
            if(f&&ff){
                return true;
            }
            return false;
        }};
    
    

• 正解

  class Solution {
  public:
      bool isSameTree(TreeNode* p, TreeNode* q) {
          if(p==nullptr&&q==nullptr){// 两棵空树
              return true;
          }
          else if(p==nullptr||q==nullptr){// 只有一棵树是空的
              return false;
          }
          else if(p->val!=q->val){// 节点值不同
              return false;
          }
          else{// 继续遍历
              return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
          }
      }
  };
  

LeetCode 100. 相同的树