快捷導(dǎo)航

C++實(shí)現(xiàn)LeetCode(100.判斷相同樹(shù))

更新時(shí)間：2021年07月21日 14:50:04 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(100.判斷相同樹(shù)),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 100. Same Tree 判斷相同樹(shù)

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
    / \       / \
2   3     2   3

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

Output: true

Example 2:

Input:     1         1
/           \
2             2

[1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
/ \       / \
2   1     1   2

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

Output: false

判斷兩棵樹(shù)是否相同和之前的判斷兩棵樹(shù)是否對(duì)稱都是一樣的原理，利用深度優(yōu)先搜索 DFS 來(lái)遞歸。代碼如下：

解法一：

class Solution {
public:
    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);
    }
};

這道題還有非遞歸的解法，因?yàn)槎鏄?shù)的四種遍歷(層序，先序，中序，后序)均有各自的迭代和遞歸的寫法，這里我們先來(lái)看先序的迭代寫法，相當(dāng)于同時(shí)遍歷兩個(gè)數(shù)，然后每個(gè)節(jié)點(diǎn)都進(jìn)行比較，可參見(jiàn)之間那道 Binary Tree Preorder Traversal，參見(jiàn)代碼如下：

解法二：

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

也可以使用中序遍歷的迭代寫法，對(duì)應(yīng)之前那道 Binary Tree Inorder Traversal，參見(jiàn)代碼如下：

解法三：

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

對(duì)于后序遍歷的迭代寫法，貌似無(wú)法只是用一個(gè)棧來(lái)做，因?yàn)槊看稳〕鰲ｍ斣睾蟛涣ⅠR移除，這樣使用一個(gè)棧的話兩棵樹(shù)結(jié)點(diǎn)的位置關(guān)系就會(huì)錯(cuò)亂，分別使用各自的棧就好了，對(duì)應(yīng)之前那道 Binary Tree Postorder Traversal，參見(jiàn)代碼如下：

解法四：

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

對(duì)于層序遍歷的迭代寫法，其實(shí)跟先序遍歷的迭代寫法非常的類似，只不過(guò)把棧換成了隊(duì)列，對(duì)應(yīng)之前那道 Binary Tree Level Order Traversal，參見(jiàn)代碼如下：

解法五：

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode*> que;
        que.push(p); que.push(q);
        while (!que.empty()) {
            p = que.front(); que.pop();
            q = que.front(); que.pop();
            if (!p && !q) continue;
            if ((p && !q) || (!p && q) || (p->val != q->val)) return false;
            que.push(p->right); que.push(q->right);
            que.push(p->left); que.push(q->left);
        }
        return true;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/100

類似題目：

Binary Tree Preorder Traversal

Binary Tree Inorder Traversal

Binary Tree Postorder Traversal

Binary Tree Level Order Traversal

參考資料：

https://leetcode.com/problems/same-tree/

https://leetcode.com/problems/same-tree/discuss/32684/My-non-recursive-method

https://leetcode.com/problems/same-tree/discuss/32687/Five-line-Java-solution-with-recursion

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(100.判斷相同樹(shù))的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)判斷相同樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: