100. Same Tree

题目 Same Tree

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

分析

判断两个二叉树是否相等,只要每个都遍历(前,中,后,层次)一下进行对比即可.
笼统的我们也可以这样认为,只要两个二叉树的根节点,左子树右子树都相等,那么这两个二叉树就相等

1,递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    //比较俩二叉树相等,只需根节点,左子树和右子树三者都相等.否则,就是不相等
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //1,边界条件判断
        if(p == null && q == null){
            return true;
        }
        
        if(p == null || q == null){
            return false;
        }
        
        //2,比较根节点
        if(p.val == q.val){
            //3,比较左右子树
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
        return false;
    }
}

时间复杂度O(n),空间复杂度O(1)

2,简洁的代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {

        if(p == null || q == null){
            return p == q;
        }  
        return (p.val == q.val) && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

时间复杂度O(n),空间复杂度O(1)