首页 > 试题广场 >

相同的二叉树

[编程题]相同的二叉树
  • 热度指数：1312 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定两个根结点分别为 root1 和 root2 二叉树，请判断这两棵树是否完全相同。
数据范围:

两棵树上的节点数目都在范围 [0, 100] 内


示例1

输入

{1,2,1},{1,#,2}

输出

false

说明



两个树在结构上不相同，故它们是不相同的。
示例2

输入

{1,2,1},{1,2,1}

输出

true

说明

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

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Java
牛客276339250号头像 牛客276339250号
直接遍历，对比节点值是否相同，如果不同返回false，然后递归遍历左节点和右节点；
import java.util.*;

/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root1 TreeNode类
* @param root2 TreeNode类
* @return bool布尔型
*/
public boolean isSameTree (TreeNode root1, TreeNode root2) {
// write code here
if(root1==null&&root2==null){
return true;
}
最初将判空的逻辑放在了root1.val != root2.va后面，造成程序抛出空指针，调整判断位置成功提交
if((root1==null&&root2!=null)||(root1!=null&&root2==null)){
return false;
}
if (root1.val != root2.val) {
return false;
}
return isSameTree(root1.left, root2.left) && isSameTree(root1.right, root2.right);
}

}
发表于 2023-11-28 10:57:31 回复(0)
fatzard头像 fatzard 
bool isSameTree(struct TreeNode* root1, struct TreeNode* root2 ) {
    if(root1==NULL&&root2==NULL)return true;
    if(root1&&root2==NULL)return false;
    if(root1==NULL&&root2)return false;
    if(root1->val!=root2->val)return false;
    return isSameTree(root1->left, root2->left)&&isSameTree(root1->right, root2->right);
}
送给考研C
发表于 2023-09-25 15:15:31 回复(0)
Rust
老刘001头像 老刘001

Rust 语言 一行解决

论 Eq 特型的正确用法~

/**
 * #[derive(PartialEq, Eq, Debug, Clone)]
 * pub struct TreeNode {
 *     pub val: i32,
 *     pub left: Option<Box<TreeNode>>,
 *     pub right: Option<Box<TreeNode>>,
 * }
 *
 * impl TreeNode {
 *     #[inline]
 *     fn new(val: i32) -> Self {
 *         TreeNode {
 *             val: val,
 *             left: None,
 *             right: None,
 *         }
 *     }
 * }
 */
struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param root1 TreeNode类 
        * @param root2 TreeNode类 
        * @return bool布尔型
    */
    pub fn isSameTree(&self, root1: Option<Box<TreeNode>>, root2: Option<Box<TreeNode>>) -> bool {
        // write code here
        root1 == root2
    }
}
发表于 2023-08-31 10:32:25 回复(0)
小谷围做题家头像 小谷围做题家 
package main
//import "fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root1 TreeNode类 
 * @param root2 TreeNode类 
 * @return bool布尔型
*/
func isSameTree( root1 *TreeNode ,  root2 *TreeNode ) bool {
    if root1==nil&&root2==nil{
        return true
    }else if root1==nil||root2==nil||root1.Val!=root2.Val{
        return false
    }else{
        return isSameTree(root1.Left,root2.Left)&&isSameTree(root1.Right,root2.Right)
    }
}

发表于 2023-01-31 22:31:55 回复(0)
C
猪猪侠新新酱头像 猪猪侠新新酱 
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root1 TreeNode类
 * @param root2 TreeNode类
 * @return bool布尔型
 */
bool preorder(struct TreeNode* root1, struct TreeNode* root2) {
    //static int count = 0;
    if (NULL != root1 && NULL != root2) {
        if (root1->val != root2->val)
            return false;
        return preorder(root1->left, root2->left)&&preorder(root1->right, root2->right) ;
        // preorder(root1->left, root2->left);
        // preorder(root1->right, root2->right);
    }
    if (NULL != root1 && NULL == root2)
        return false;
    if (NULL == root1 && NULL != root2)
        return false;
    return true;
}
bool isSameTree(struct TreeNode* root1, struct TreeNode* root2 ) {
    // write code here
    // if(!root1 && !root2)
    //     return true;
    // if(!root1 || !root2)
    //     return false;
    // if(root1->val!=root2->val)
    //     return false;
    // return isSameTree(root1->left,root2->left)&&isSameTree(root1->right,root2->right);
    return preorder(root1, root2);
}

发表于 2023-01-10 17:21:15 回复(0)
牛客904485203号头像 牛客904485203号 
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    bool isSameStucture(TreeNode* p1, TreeNode* p2) {
        // check root
        if (p1 == nullptr && p2 == nullptr) {
            return true;
        } else if (p1 == nullptr || p2 == nullptr) {
            return false;
        }
        // check left child
        if (p1 -> left == nullptr && p2 -> left == nullptr) {
            ;
        } else if (p1 -> left == nullptr || p2 -> left == nullptr) {
            return false;
        }
        // check right child
        if (p1 -> right == nullptr && p2 -> right == nullptr) {
            ;
        } else if (p1 -> right == nullptr || p2 -> right == nullptr) {
            return false;
        }

        return true;
    }
    bool isSameTree(TreeNode* root1, TreeNode* root2) {
        // write code here
        if (!isSameStucture(root1, root2)) {
            return false;
        }

        stack<TreeNode*> s1, s2;
        s1.push(root1);
        s2.push(root2);

        TreeNode* cur1 = nullptr, *cur2 = nullptr;
        while (!s1.empty() || !s2.empty()) {
            cur1 = s1.top();
            s1.pop();
            cur2 = s2.top();
            s2.pop();
            while (cur1 != nullptr || cur2 != nullptr) {
                if (!isSameStucture(cur1, cur2)) {
                    return false;
                }
                // visit nodes
                if (cur1 -> val != cur2 -> val) {
                    return false;
                }
                // push right child into stack
                if (cur1 -> right != nullptr) {
                    s1.push(cur1 -> right);
                    s2.push(cur2 -> right);
                }

                cur1 = cur1 -> left;
                cur2 = cur2 -> left;
            }
        }
        return true;
    }
};

发表于 2022-10-22 11:42:16 回复(0)
Java
BlueProtocol头像 BlueProtocol 
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    public boolean isSameTree (TreeNode root1, TreeNode root2) {
        // write code here
        	Queue<TreeNode> rootQueue1 = new LinkedList<>();
		Queue<TreeNode> rootQueue2 = new LinkedList<>();
		rootQueue1.offer(root1);
		rootQueue2.offer(root2);
		while (!rootQueue1.isEmpty() && !rootQueue2.isEmpty()) {
			TreeNode poll1 = rootQueue1.poll();
			TreeNode poll2 = rootQueue2.poll();
            if(poll1 == null && poll2 == null) {
			 continue;
            }
			if (poll1 == null || poll2 == null ||  poll1.val != poll2.val) {
				return false;
			}
			rootQueue1.offer(poll1.left);
			rootQueue1.offer(poll1.right);
			rootQueue2.offer(poll2.left);
			rootQueue2.offer(poll2.right);
		}
		return true;
    }
}

发表于 2022-08-18 23:10:32 回复(0)
C++
zhengluoqi头像 zhengluoqi 
bool isSameTree(TreeNode* root1, TreeNode* root2) {
    if(!root1&&!root2)return true;
    if(!root1||!root2)return false;
    if(root1->val!=root2->val)return false;
    return isSameTree(root1->left,root2->left)&&isSameTree(root1->right,root2->right);
    }


发表于 2022-07-26 16:31:27 回复(0)
Java
暴风陨石坠头像 暴风陨石坠 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    public boolean isSameTree (TreeNode root1, TreeNode root2) {
        if(root1 != null && root2 == null || root1 == null && root2 != null) return false;
        if(root1 == null && root2 == null) return true;
        if(root1.val != root2.val) return false;
            return isSameTree(root1.left,root2.left) && isSameTree(root1.right,root2.right);
      
    }
}

发表于 2022-07-12 16:49:57 回复(0)
C++
coder6458头像 coder6458
 vector<int>res;
      vector<int>ans;
    void getvec(TreeNode* root,vector<int>&a){
         if(root==NULL) return ;
        a.push_back(root->val);
        getvec(root->left,a);
        getvec(root->right,a);
    }
    bool isSameTree(TreeNode* root1, TreeNode* root2) {
        // write code here
       getvec(root1,res);
        getvec(root2,ans);
        if(ans==res) return true;
        return false;
        
    }
发表于 2022-07-09 15:04:45 回复(0)
C++
tq要上榜头像 tq要上榜
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    bool isSameTree(TreeNode* root1, TreeNode* root2) {
        // write code here
        
        if(root1 && root2 && root1->val != root2->val) return false;
        if(root1==nullptr && root2 != nullptr) return false;
        if(root1!=nullptr && root2 == nullptr) return false;
        if(!root1 && !root1) return true;
        queue<TreeNode*>q1;
        queue<TreeNode*>q2;
        q1.push(root1);
        q2.push(root2);
        
        while(!q1.empty() && !q2.empty())
        {
            TreeNode* p1 = q1.front();
            TreeNode* p2 = q2.front();
            q1.pop();
            q2.pop();
            
            if(p1->left && p2->left && p1->left->val==p2->left->val)
            {
                 q1.push(p1->left);
                 q2.push(p2->left);
            }
            else if(p1->left && p2->left && p1->left->val!=p2->left->val)
                return false;
      
            if(p1->right && p2->right && p1->right->val==p2->right->val)
            {
                 q1.push(p1->right);
                 q2.push(p2->right);
            }
            else if(p1->right && p2->right && p1->right->val!=p2->right->val)
                return false;
        }
        
        if(q1.empty() && q2.empty())
        return true;
        else
        return false;
    }
};
发表于 2022-07-06 13:16:50 回复(0)
Java
訾尤头像 訾尤
public boolean isSameTree (TreeNode root1, TreeNode root2) {
        // 如果两棵树都为空返回true
        if (root1 == null && root2 == null) {
            return true;
        }
        // 如果其中一棵树为空返回false
        if (root1 == null || root2 == null) {
            return false;
        }
        // 如果两个节点值不相同返回false
        if (root1.val != root2.val) {
            return false;
        }
        // 递归
        return isSameTree(root1.left, root2.left) && isSameTree(root1.right, root2.right);
    }
发表于 2022-04-27 15:11:02 回复(0)
提交观点

问题信息

树 dfs 广度优先搜索(BFS)
难度：
12条回答 2178浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号