您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

相同的树(图文)

第十三双眼睛2023-11-26【数据结构与算法】人已围观

简介相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

本来想的是，利用某种遍历方式，前序，中序，或者后续，将每个二叉树的节点元素拼接成一个字符串，来比较字符串是否相同，但是有一个问题，比如一个二叉树的左子节点为1，右子节点为null，而另一个二叉树的左子节点为null，右子节点为1，这样得到字符串是相同的，但是结果是错的，因此这种方式不可行。

因此，得遍历两个二叉树，如果根节点都为null，则相同，如果一个为null，另一个不为null，则不相同，如果都不为null，则比较节点得值是否相同，如果不相同，则不相同，如果相同，则递归比较他们得左子树，和右子树。代码如下：

class TreeNode1 {
int val;
TreeNode1 left;
TreeNode1 right;
TreeNode1() {}
TreeNode1(int val) { this.val = val; }
TreeNode1(int val, TreeNode1 left, TreeNode1 right) {
this.val = val;
this.left = left;
this.right = right;
}
}

public static boolean isSame(TreeNode1 p, TreeNode1 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 {
       return isSame(p.left, q.left) && isSame(p.right, q.right);
   }
}

Tags：

很赞哦！ ()

上一篇：二叉树的中序遍历(图文)

下一篇：对称二叉树(图文)