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