频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
LeetCode 100 Same Tree(相同树判断)(二叉树、递归、栈和队列、深搜和宽搜)
2016-01-12 09:20:53         来源:nomasp柯于旺  
收藏   我要投稿

翻译

给定两个二叉树,写一个函数检查他们是否相等。

两个二叉树如果结构上相同并且有相同的值,那么就认定他们是相等的。

原文

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> myStack;
    myStack.push(pair(p, q));
    while (!myStack.empty()) {
        p = myStack.top().first;
        q = myStack.top().second;
        if (!p ^ !q || (p && q && p->val != q->val))
            break;
        myStack.pop();
        if (p && q) {
            myStack.push(pair(p->left, q->left));
            myStack.push(pair(p->right, q->right));
        }
    }
    return myStack.empty();
}       

BFS + queue

bool isSameTree(TreeNode* p, TreeNode* q) {
    queue> myQueue;
    myQueue.push(pair(p, q));
    while (!myQueue.empty()) {
        p = myQueue.front().first;
        q = myQueue.front().second;
        if (!p ^ !q || (p && q && p->val != q->val))
            break;
        myQueue.pop();
        if (p && q) {
            myQueue.push(pair(p->right, q->right));
            myQueue.push(pair(p->left, q->left));                 
        }
    }
    return myQueue.empty();
}

点击复制链接 与好友分享!回本站首页
相关TAG标签 递归 队列
上一篇:LeetCode Spiral Matrix
下一篇:LeetCode Jump Game II
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站