100. 相同的樹

• 題目要求
  給出兩二叉樹，詢問這兩棵樹是否完全相同，輸出true或者false

• 題目思路(我的，不知道是否可行，目前仍然是wa，QAQ，成功實現，通過兩次不同\(DFS\)遍歷的方式[其中必須包含中序遍歷]，來確定一棵樹，保證其的唯一性)

  • 先知條件：如果已知先序遍歷(\(DLR\))和中序遍歷(\(LDR\))或者后序遍歷(\(LRD\))和中序遍歷(\(LDR\))

  • 那么我通過\(4\)個\(DFS\)深度遍歷兩棵樹\(TreeNode\) \(p\),\(TreeNode\) \(q\)
    分別得到相應的中序遍歷和先(后)序遍歷，最后再兩個\(for\)循環進行遍歷判斷是否相同

  • 代碼如下(未實現)

    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()){
                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;
        }};
    

  • 按照自己的思路，再次實現(AC)

    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){lrp[0].push_back(-1);return;}
            dfs_lrp1(root->left);
            dfs_lrp1(root->right);
            lrp[0].push_back(root->val);
        }
        void dfs_lrp2(TreeNode* root){
            if(!root){lrp[1].push_back(-1);return;}
            dfs_lrp2(root->left);
            dfs_lrp2(root->right);
            lrp[1].push_back(root->val);
        }
        void dfs_lpr1(TreeNode* root){
            if(!root){lpr[0].push_back(-1);return;}
            dfs_lpr1(root->left);
            lpr[0].push_back(root->val);
            dfs_lpr1(root->right);
        }
        void dfs_lpr2(TreeNode* root){
            if(!root){lpr[1].push_back(-1);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()){
                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);
          }
      }
  };