題目 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.

分析

判斷兩個二叉樹是否相等,只要每個都遍歷(前,中,后,層次)一下進(jìn)行對比即可.
籠統(tǒng)的我們也可以這樣認(rèn)為,只要兩個二叉樹的根節(jié)點(diǎn),左子樹右子樹都相等,那么這兩個二叉樹就相等

1,遞歸

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    //比較倆二叉樹相等,只需根節(jié)點(diǎn),左子樹和右子樹三者都相等.否則,就是不相等
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //1,邊界條件判斷
        if(p == null && q == null){
            return true;
        }
        
        if(p == null || q == null){
            return false;
        }
        
        //2,比較根節(jié)點(diǎn)
        if(p.val == q.val){
            //3,比較左右子樹
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
        return false;
    }
}

時間復(fù)雜度O(n),空間復(fù)雜度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);
    }
}

時間復(fù)雜度O(n),空間復(fù)雜度O(1)