LeetCode 100. 相同的树（二叉树遍历）

Michael阿明

发布于 2021-02-19 22:06:04

28300

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

1. 题目

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

2. 解题

2.1 递归

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q)
        	return true;
        bool ans = true;
        same(p,q,ans);
        return ans;
    }
    void same(TreeNode* r1, TreeNode* r2, bool &ans) 
    {
    	if(ans == false)
    		return;
    	if(!r1 && !r2)
		{
			ans = true;
			return;
		}
    	if(r1 && r2 && r1->val == r2->val)
    	{
    		same(r1->left,r2->left,ans);
    		same(r1->right,r2->right,ans);
    	}
    	else
    		ans = false;
    }
};

2.2 按层遍历

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/09/15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树