每日算法-相同的树

题目

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

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

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

• 两棵树上的节点数目都在范围 [0, 100] 内
• -104 <= Node.val <= 104

解法

思路： 递归。详细解释看代码中注释。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 解法：递归
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 判断p和q是否为空，只有当两个都同时为空的时候返回true；若一方为空，另一方不为空，返回false。
        if(p == null || q == null){
            if(p != null || q != null){
                return false;
            } else {
                return true;
            }
        }
        // 判断值是否相等，不相等返回false，相等继续往下判断。
        int valP = p.val;
        int valQ = q.val;
        if(valP != valQ){
            return false;
        }
        // 判断left节点是否相等，不相等返回false，相等继续往下判断。
        TreeNode leftP = p.left;
        TreeNode leftQ = q.left;
        if(!isSameTree(leftP,leftQ)){
            return false;
        }
        // 判断right节点是否相等，不相等返回false。
        TreeNode rightP = p.right;
        TreeNode rightQ = q.right;
        if(!isSameTree(rightP,rightQ)){
            return false;
        }
        // 前面都是相等的，返回true即可。
        return true;
    }
}

总结

本篇文章讲解了算法题目的思路和解法，代码和笔记由于纯手打，难免会有纰漏，如果发现错误的地方，请第一时间告诉我，这将是我进步的一个很重要的环节。以后会定期更新算法题目以及各种开发知识点，如果您觉得写得不错，不妨点个关注，谢谢。

最后

以上就是开放美女为你收集整理的每日算法-相同的树的全部内容，希望文章能够帮你解决每日算法-相同的树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。