1

分享

100. Same Tree(C++)

100. Same Tree、LeetCode、深度優先搜尋DFS(Depth-first search)
筆記

100. Same Tree

題目:給定兩棵二元樹 p 和 q 的根,編寫一個函數來檢查它們是否相同。 如果兩個二叉樹在結構上相同,並且節點具有相同的值,則認為它們是相同的。
回傳:bool值,True or False
例如1:
Input:p = [1,2,3], q = [1,2,3]
  •    1
  •   / \
  • 2    3
  

Output : true

例如2:
Input:p = [1,2], q = [1,null,2]
  •    1        1
  •   /        /  \ 
  • 2     null   2  
  

Output : false

Code

深度優先搜尋 DFS(Depth-first search)
  • 比對是否不一樣,直到,比對到最後p和q都指向null,回傳true
  

    if(!p && !q){

        return true;

    }

    if(p && !q || !p && q || p->val != q->val){

        return false;

    }

  • 往下一層搜尋,左邊(left)與右邊(right),分開比對
  

    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);

  • 完整code
  

//  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) {}

};


bool isSameTree(TreeNode* p, TreeNode* q) {

    if(!p && !q){

        return true;

    }

    if(p && !q || !p && q || p->val != q->val){

        return false;

    }

    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);

}


參考資料

[1]. Same Tree - LeetCode
[2]. [LeetCode] 100. Same Tree 判断相同树 - Grandyang - 博客园 (cnblogs.com)
#筆記  #leetcode 
分類:學習

【關鍵字】:新手教學、Leetcode ; 【分類】:學習、理財。(目前C++新手教學第二章內容已完結)。建議或意見可私訊:https://reurl.cc/ze7L9k。文章有錯誤的地方還請留言指正,謝謝各位

評論
上一篇
  • 下一篇
  • Struct結構體 (C++)
  • 更多文章
    載入中... 沒有更多了