LeetCode 100 Same Tree（相同樹判斷）（二叉樹、遞歸、棧和隊列、深搜和寬搜）

LeetCode 100 Same Tree（相同樹判斷）（二叉樹、遞歸、棧和隊列、深搜和寬搜）

翻譯

給定兩個二叉樹，寫一個函數檢查他們是否相等。

兩個二叉樹如果結構上相同並且有相同的值，那麼就認定他們是相等的。

原文

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

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

分析

還是先用一貫用的遞歸解出來好了。

結構上一致指的是A樹有左節點，B樹也有左節點這種。用這個可以一次性判斷出來：

if ((node1->left && node2->left) && (node1->right && node2->right)) {
}

不過不能同時得到節點是否存在，以後後面求值的時候如果節點不存在卻去求值是會出問題的，所以還是老老實實用好幾個if來判斷好了。

bool isSameNode(TreeNode *node1, TreeNode *node2) {
    if (node1->val == node2->val) {
        bool b1 = false, b2 = false;
        TreeNode *temp1 = node1->left;
        TreeNode *temp2 = node2->left;
        if (temp1 != NULL && temp2 != NULL) {
            b1 = isSameNode(temp1, temp2);
        }
        else if (temp1 == NULL && temp2 == NULL) {
            b1 = true;
        }
        TreeNode *temp3 = node1->right;
        TreeNode *temp4 = node2->right;
        if (temp3 != NULL && temp4 != NULL) {
            b2 = isSameNode(temp3, temp4);
        }
        else if (temp3 == NULL && temp4 == NULL) {
            b2 = true;
        }
        return b1 && b2;
    }
    else {
        return false;
    }
}

bool isSameTree(TreeNode *p, TreeNode *q) {
    if (p != NULL && q != NULL)
        return isSameNode(p, q);
    else if (p == NULL && q == NULL) return true;
    else return false;
}

然後繼續來壓縮壓縮，上面這麼多廢話，對於a, b兩個結點無非就是5種情況：

補充說明：由於Markdown制作表格的格式原因，第二和第三行代碼的“||”均用或字來表示。

bool isSameTree(TreeNode *p, TreeNode *q) {
    if (p == NULL && q == NULL) return true;
    else if (p == NULL || q == NULL) return false;
    else if (p->val != q->val) return false;
    else isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

代碼

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if (p == NULL && q == NULL) return true;
        else    if ((p == NULL || q == NULL) || (p->val != q->val)) return false;
        else isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

進階

還是沒能寫出來，看看大神們寫的，繼續膜拜，繼續加油！

DFS + stack

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

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