Leetcode相同的树

绝地灬酷狼 2022-09-09 14:42 119阅读 0赞

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

如下面的两颗二叉树：结构相同，而且对应节点的值是相同的

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_18_color_FFFFFF_t_70_g_se_x_16][]

如下面的二叉树，结构不同，所以不能算为是相同的二叉树

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16][]

再比如下面的二叉树，虽然结构相等，但是值不相等，也不能算为相同的二叉树

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16 1][]

**详细题解**

一、基于递归的解决方法

递归函数

public boolean isSameTree(TreeNode p, TreeNode q) {
    
    }

终止条件

（1） p == null && q == null 时，p代表的树和q代表的树是一颗空树，自然是相同的树

（2） p == null || q == null 时，表示树的结构不一样，自然不是相同的树

（3） p.val != q.val时，表示树的结构一样，但是对于的值不相等，不是相同的树

状态转换方程

p代表的树和q代表的树相同，可以转换为 p 与 q相同，同时p.left 代表的树 和 q.left 代表的树相同，同时 p.right 代表的树 和 q.right 代表的树相同。

经过上面的分析，其实代码很好写出来，最终的代码如下：

public boolean isSameTree(TreeNode p, TreeNode q) {
            // p 和 q 代表的树都是空树
            if(p == null && q == null) return true;
    
            // p 和 q 代表的树结构不相同，或者是值不相等
            if(p == null || q == null || p.val != q.val) return false;
    
            // 需同时满足p.left 和 q.left 相同，同时p.right 和 q.right 相同
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }

二、基于队列的解决方案

其实可以对整颗树执行遍历，按照同样的结构进行遍历，对遍历到的每一个节点都判断是否相等即可，无论采用前序遍历或者是中序遍历或者是后续遍历都是可以的，代码如下：

public boolean isSameTree(TreeNode p, TreeNode q) {
    //定义两个队列
            Queue<TreeNode> queue_p = new LinkedList<>();
            queue_p.add(p);
    
            Queue<TreeNode> queue_q = new LinkedList<>();
            queue_q.add(q);
    
            while (!queue_p.isEmpty() || !queue_q.isEmpty()) {
                TreeNode pNode = queue_p.poll();
                TreeNode qNode = queue_q.poll();
                if (pNode == null && qNode == null) continue;
                if (pNode == null || qNode == null || pNode.val != qNode.val) return false;
                queue_p.add(pNode.left);
                queue_q.add(qNode.left);
    
                queue_p.add(pNode.right);
                queue_q.add(qNode.right);
            }
    
            return true;
        }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/92166296c47e4b169d474c0c6bbd9e9b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/0c1486f5f2cf4e0cb2c6654b1c334183.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_16_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/8677f7c9b0484ba9bc865aa6edde51d9.png