程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 100 Same Tree(相同樹判斷)(二叉樹、遞歸、棧和隊列、深搜和寬搜)

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

編輯:C++入門知識

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種情況:

節點a的情況 節點b的情況 相關代碼 空 空 if (p == NULL && q == NULL) return true; 非空 空 else if (p == NULL 或 q == NULL) return false; 空 非空 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);

補充說明:由於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

BFS + queue

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved